BOJ 7785 : 회사에 있는 사람 (Hash Table + Merge Sort)

삼성 B형 전체 링크

 

www.acmicpc.net/problem/7785

 

 

이름을 입력받으면, 아래의 DB 배열에 저장하고 in = 1로 두자.

typedef struct st
{
	char name[6];
	int in;
}DB;

 

DB에 저장하고 이름을 hashing하여 HashTable에 저장하는데, 이때, DB를 포인터로 가르키도록 하자.

typedef struct st2
{
	DB *db;
	struct st2 *next;
}HASH;

즉, Hash에서 db를 보고 있으므로, 포인터로 접근하여 in = 0으로 바꿀 수 있게 된다.

DB 자체는 배열로 유지하되, in을 Hash를 통해 포인터로 값을 바꾼다.

 

input = 'enter'면 Hash 저장 및 in = 1, 

input = 'leave'면 Hash 탐색 및 in = 0, 이 된다.

 

마지막으로 DB에서 회사에 남은 사람만 복사하고, Merge Sort를 이용해 정렬하자.

for (int i = 0; i < pcnt; i++)
	if (dbList[i].in) enterList[inCnt++] = dbList[i];

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX_TABLE (1000003)
typedef unsigned long long int ull;

int N;

typedef struct st
{
	char name[6];
	int in;
}DB;

DB dbList[1001000];    /* 전체 사람을 관리하는 list */
DB enterList[1001000]; /* 회사에 남은 사람을 저장할 list */

typedef struct st2
{
	DB *db;
	struct st2 *next;
}HASH;

HASH Hash[MAX_TABLE];
HASH POOL[MAX_TABLE];
int pcnt;

ull hash(const char *str)
{
	ull hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

void mystrcpy(char *a, char *b)
{
	while (*a++ = *b++);
}

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

DB b[1000100];
void merge(int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (mystrcmp(enterList[i].name, enterList[j].name) > 0) b[k++] = enterList[i++];
		else b[k++] = enterList[j++];
	}

	while (i <= mid) b[k++] = enterList[i++];
	while (j <= end) b[k++] = enterList[j++];
	for (i = start; i <= end; i++)
		enterList[i] = b[i - start];
}

void sort(int start, int end)
{
	int mid;
	if (start == end) return;

	mid = (start + end) >> 1;
	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}

int main()
{
	int count, inCnt;
	char name[6], cmd[6];

	scanf("%d", &N);

	count = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%s %s", name, cmd);
		if (!mystrcmp(cmd, (char*)"enter")) /* enter 입력 */
		{
        	mystrcpy(dbList[count].name, name); /* DB에 순서대로 저장 */
			dbList[count].in = 1; /* in = 1 표시 */

			ull h = hash(name);

			HASH *nd = &POOL[pcnt++]; /* 해시 테이블에 연결 */
			nd->db = &dbList[count];

			nd->next = Hash[h].next;
			Hash[h].next = nd;

			count++;
		}
		else /* leave 입력 */
		{
			ull h = hash(name);

			HASH *nd = Hash[h].next;

			while (nd)
			{
				if (!mystrcmp(nd->db->name, name) && nd->db->in) /* 이름이 같고 in = 1이면 */
				{
					nd->db->in = 0; /* in = 0 으로 변경 */
					break;          /* 동명이인이 없으므로 종료 */
				}

				nd = nd->next;
			}
		}
	}

	inCnt = 0;
	for (int i = 0; i < pcnt; i++)
		if (dbList[i].in) enterList[inCnt++] = dbList[i];
	
	sort(0, inCnt);

	for (int i = 0; i < inCnt; i++)	printf("%s\n", enterList[i].name);

	return 0;
}

---

위의 코드는 in이라는 flag를 통해 Hash에서 Node를 "삭제" 된 것처럼 만들었다.

실제로 삭제를 하면 다음 Hash에서 Node가 삭제되었으므로, 탐색을 줄일 수 있다.

(node 삭제 예시는 링크 참고)

 

아래는 leave한 사람을 다음 해시에서 찾지 못하도록 node를 삭제하는 코드다.

int main()
{
	/* ... */
    
	for (int i = 0; i < N; i++)
	{
		scanf("%s %s", name, cmd);
		if (!mystrcmp(cmd, (char*)"enter"))
		{
			/* enter가 들어온 경우 */
		}
		else
		{
			ull h = hash(name);

			HASH *nd = &Hash[h]; /* Hash[h].next가 아닌 head 자체의 주소를 받는다 */

			while (nd->next) /* next가 null인지 check 해야된다 */
			{
				if (!mystrcmp(nd->next->db->name, name))
				{
					nd->next->db->in = 0; /* 0으로 바꿔야 enterList에서 무시할 수 있다 */
					nd->next = nd->next->next; /* node의 삭제, 다음 hash에서는 탐색이 불가 */
					break;
				}

				nd = nd->next;
			}
		}
	}

	inCnt = 0;
	for (int i = 0; i < pcnt; i++)
		if (dbList[i].in) enterList[inCnt++] = dbList[i];
    
    /* ... */
    
}

 

삭제를 할 경우, nd = Hash[h].next 에서 &Hash[h]로 바뀐것에 주의해야된다.

nd는 포인터인데, 자기 자신을 삭제를 할 수는 없다.

nd->next = nd->next->next에 의해 자기 자신의 다음 node만 삭제가 가능하다.

 

따라서 이전 코드에서 nd가 nd->next로 바뀐다.

자기 자신을 삭제하고 싶으면 prev로 이전 nd를 저장해둬야 한다.

 

하지만 현재 방법으로도 B형의 모든 Linked List 문제를 풀 수 있으므로, 1가지 방법만 기억해두자.

(궁금하면 prev, cur, linked list 검색)