BOJ 1764 : 듣보잡 (Hash Table + Merge Sort)

삼성 B형 전체 링크

 

www.acmicpc.net/problem/1764

 

 

듣도 못한 사람의 수 N명,

보도 못한 사람의 수 M명 중

두 명단에 모두 포함되는 사람의 수를 찾고, 사전순으로 출력해야 한다.

 

두 명단에 포함 → Hash Table

사전순 출력 → Merge Sort

 

꼭 이렇게 풀 필요는 없지만, B형 연습을 위해 Hash Table + Merge Sort로 풀어보자.

 

B형에서는 string 라이브러리를 사용할 수 없으므로, strcmp와 strcpy는 직접 만들어야 된다.

(가끔 코드로 제공)

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;
}

 

먼저, 듣도 못한 사람의 수 N명에 대해 Hash Table을 만들어 둔다.

for (int i = 0; i < N;i++) /* N명의 듣도 못한 놈 */
{
	scanf("%s", str);
	ull h = hash(str); /* 이름을 hashing하여 hash table에 저장 */

	nd = &POOL[pcnt++];
	mystrcpy(nd->name, str);

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

 

그리고, 보도 못한 명단을 M번 입력 받으면서, name을 hashing 하여 Hash Table을 검색한다.

듣도 못한 Hash Table에서도 키 충돌이 일어날 수 있으므로, 모든 Link를 뒤지면서 이름이 실제로 같은지 확인한다.

이름이 같다면, 듣보잡 List에 명단을 추가한다.

for (int i = 0; i < M;i++) /* M명의 보도 못한 놈 */
{
	scanf("%s", str);
	ull h = hash(str); /* hash table에 저장하지 않고 바로 탐색한다 */

	for (nd = Hash[h].next; nd; nd = nd->next)
	{
		if (!mystrcmp(nd->name, str)) /* 이름이 같으면 */
			DBJ_List[listcnt++] = nd->name; /* 듣보잡 리스트, 이름을 포인터로 가르키자 */
	}
}

여기에서 char 2차원 배열에 이름을 copy할 수도 있지만, pointer를 선언해서 가르키게만 하면

copy에 대한 비용을 0으로 만들 수 있다.

 

실제 문자열 비교는 포인터로 하면 된다.

 

이제 듣보잡 List가 완성되었으니, Merge Sort로 정렬만 해주면 된다.

 

최종 코드는 아래와 같다. Merge Sort의 비교 부분이 strcmp로 바뀌었다.

#include <stdio.h>

#define MAX_TABLE (1000007)

typedef unsigned long long int ull;
int N, M;

typedef struct st
{
	char name[21];
	struct st *next;
}HASH;

HASH Hash[MAX_TABLE];
HASH POOL[500000 + 50000];
int pcnt;

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;
}

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

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

	return hash % MAX_TABLE;
}

char* DBJ_List[500000 + 5000]; /* 듣보잡 List */
char* b[500000 + 5000]; /* merge sort temp 배열 */
int listcnt;

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(DBJ_List[i], DBJ_List[j]) < 0) b[k++] = DBJ_List[i++];
		else b[k++] = DBJ_List[j++];
	}

	while (i <= mid) b[k++] = DBJ_List[i++];
	while (j <= end) b[k++] = DBJ_List[j++];
	for (i = start; i <= end;i++)
		DBJ_List[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(void)
{
	HASH *nd;
	char str[21];

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N;i++)
	{
		scanf("%s", str);
		ull h = hash(str);

		nd = &POOL[pcnt++];
		mystrcpy(nd->name, str);

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

	for (int i = 0; i < M;i++)
	{
		scanf("%s", str);
		ull h = hash(str);

		for (nd = Hash[h].next; nd; nd = nd->next)
		{
			if (!mystrcmp(nd->name, str))
				DBJ_List[listcnt++] = nd->name;
		}
	}

	sort(0, listcnt - 1);

	printf("%d\n", listcnt);
	for (int i = 0; i < listcnt;i++) printf("%s\n", DBJ_List[i]);

	return 0;
}

---

실제 B형에서는 pcnt, listcnt, Hash 모두 초기화를 해주자.