KU COSE101 2018기말고사 6번 문제

2016 기출	1번	2번	3번	4번	5번
2017 기출	1번	2번	3번	4번	5번
2018 기출	1번	2번	3번	4번	5번	6번

기존 기출 문제에 오류가 있어 약간 수정하였습니다.

보안상 특별한 방에 입실할 때 id를 입력하면 id 별로 입실 횟수를 기록하는 시스템을 개발하였다. 이 시스템은 예를 들어 최근 6회의 입실 기록을 다음과 같이 보여준다. 여기서 -1은 입실기록의 끝을 나타낸다.

Enter id: 6927238
Enter id: 3428529
Enter id: 2800555
Enter id: 2900123
Enter id: 3428529
Enter id: 6927238
Enter id: -1
id: 2800555 (1)
id: 2900123 (1)
id: 3428529 (2)
id: 6927238 (2)

이 프로그램은 다음 그림 1과 같이 linked list 구조를 이용하여 출입을 관리하고, linked list는 id를 등록할 때 항상 정렬된 상태를 유지한다.

#include<stdio.h>
#include<stdlib.h>

struct Node{
	int id;
	int count;
	struct Node* next;
};

typedef struct Node* NodePtr;

NodePtr head;

void print_report() {
	for(NodePtr p = head->next ; p!=NULL; p = p->next) {
		printf("id: %d (%d)\n",p->id, p->count);
	}
}

void record_entry(int id) {

}

int main()
{
	int id;
	for(;;){
		printf("Enter id: ");
		scanf("%d", &id);
		if(id < 0) break;
		record_entry(id);
	}
	print_report();
}

---

예시풀이

void record_entry(int id) {
	NodePtr newPtr = (NodePtr)malloc(sizeof(struct Node));
	
	newPtr->id = id;
	newPtr->count = 1;
	newPtr->next = NULL;
	
	if(head == NULL){
		head = (NodePtr)malloc(sizeof(struct Node));
		head->next = newPtr;
		return;	
	}
	
	NodePtr prev = head;
	NodePtr cur = head->next;
	while(cur != NULL){
		if(cur->id == newPtr->id) {
			(cur->count)++;
			break;
		}
		if(cur->next == NULL){
			cur->next = newPtr;
			break;
		}
		if(cur->id > newPtr->id) {
			prev->next = newPtr;
			newPtr->next = cur;
			break;
		}
		prev = cur;
		cur = cur->next;
	}
}

newPtr로 이번에 들어온 id에 대한 정보를 저장해준다.

if(head==NULL) : 만약에 이번이 첫 노드라면, head에게 메모리를 지정해주고 그 다음 노드를 이번에 만든 노드로 저장해준다.


만약에 이번이 첫 노드가 아니라면, prev에 head, cur에 head다음 노드를 넣어준다.
그리고 linked list 를 순회하는 동안 값을 넣어줄 위치를 찾는다.

1. 동일한 값이 이미 존재할 경우, count를 올려주고 break한다.
2. 이번에 넣을 값이 지금껏 존재하던 값 중 가장 큰 값인 경우 (cur->next == NULL), 마지막 노드에 newPtr를 넣어주고 break 한다.
3. 1, 2경우가 아닌 일반적인 경우, cur의 값이 나보다 큰 값이 나오는 경우, prev의 다음에 newPtr을, newPtr의 다음에 cur을 연결해주고 break한다.