[Algorithm][C++] BOJ 1764: 듣보잡 (Hash Table + Merge Sort)

url: https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

풀이 핵심

1. 삼성 B형 시험에 대비해 Hash Table과 Merge Sort를 활용해 본 문제를 풀어보자

Hash Table 구현은 다음 링크를 참조하자. 

 

2. Merge Sort 구현은 피로물든딸기님의 블로그를 참고했다.

 

코드

#include <cstdio>
#define MAX_TABLE	100007
#define MAX			500005

typedef unsigned long long ull;
int N, M;

struct Hash {
	char name[21];
	Hash* next;
};
Hash hash_table[MAX_TABLE];
Hash pool[MAX];
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, const char* b) {
	while (*a++ = *b++);
}

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

char* dbj_list[MAX];
char* temp[MAX];
int lcnt;

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) temp[k++] = dbj_list[i++];
		else temp[k++] = dbj_list[j++];
	}

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

	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_table[h].next;
		hash_table[h].next = nd;
	}
	for (int i = 0; i < M; i++) {
		scanf("%s", str);
		ull h = hash(str);

		for (nd = hash_table[h].next; nd; nd = nd->next) {
			if (!mystrcmp(nd->name, str)) {
				dbj_list[lcnt++] = nd->name;
			}
		}
	}
	sort(0, lcnt - 1);
	printf("%d\n", lcnt);
	for (int i = 0; i < lcnt; i++) {
		printf("%s\n", dbj_list[i]);
	}
	return 0;
}