[Algorithm][C++] BOJ 20920: 영단어 암기는 괴로워 (Hash Table + Heap)

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

20920번: 영단어 암기는 괴로워

 

풀이 핵심

1. Hash Table을 활용해 단어가 중복되서 나온 것인지 판단한다. Heap에 우선순위 (단어가 나온 횟수, 단어 길이, 알파벳 역순)을 유지 될 수 있도록 해서 마지막에 HeapPop을 이용해 정답을 출력한다. 여기서 단어가 나온 횟수가 클수록, 단어 길이가 길수록 알파벳 역순 일 수록 부모 노드 (1에 가깝게)가 되도록 push, pop을 구성한다.

 

2. 단어가 중복되어 나왔다고 판단 되면 현재 이 단어의 힙 노드 위치를 리턴해주는 isExist 함수를 만든다. (힙 노드의 각각 위치를 저장 할 수있는 wordIDList를 만들어 저장한다) 힙 노드 위치로 단어에 접근해서 횟 수를 증가시키고 다시 정렬해주는 update 함수를 만든다.

void update(int wID) {
	int current = heapIDList[wID];
	int parent = current / 2;
	heap[current]->count += 1;
	
	while (parent > 0) {
		if (comp(heap[current], heap[parent]) > 0) break;
		heapIDList[heap[current]->wID] = parent;
		heapIDList[heap[parent]->wID] = current;
		
		Word* tmp = heap[current];
		heap[current] = heap[parent];
		heap[parent] = tmp;

		current = parent;
		parent = current / 2;
	}
}

int isExist(const char* str, ull h) {
	Node* nd = hashTable[h].next;

	while (nd != 0) {
		if (!mystrcmp(wordList[nd->wID].str, str)) return nd->wID;
		nd = nd->next;
	}
	return 0;
}

 

전체 코드

#include <cstdio>
#define MAXN		100001
#define MAX_TABLE	100007
typedef unsigned long long ull;

int N, maxLength;
struct Word {
	int wID;
	char str[11];
	int length;
	int count;
};

Word wordList[MAXN];
Word* heap[MAXN];
int heapIDList[MAXN];
int hSize;

struct Node {
	int wID;
	Node* next;
};
Node nodePool[MAXN];
int pcnt;
Node hashTable[MAX_TABLE];

int mystrlen(const char* str) {
	int len = 0;
	while (*str++) ++len;
	return len;
}

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

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

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

int comp(Word* a, Word* b) {
	if (a->count == b->count) {
		if (a->length == b->length) {
			return mystrcmp(a->str, b->str);
		}
		return b->length - a->length;
	}
	return b->count - a->count;
}

void heapPush(Word* w) {
	if (hSize == MAXN - 1) return;
	heap[++hSize] = w;
	heapIDList[w->wID] = hSize;
	int current = hSize;
	int parent = hSize / 2;

	while (parent > 0) {
		if (comp(heap[current], heap[parent]) > 0) break;
		heapIDList[heap[current]->wID] = parent;
		heapIDList[heap[parent]->wID] = current;

		Word* tmp = heap[current];
		heap[current] = heap[parent];
		heap[parent] = tmp;

		current = parent;
		parent = current / 2;
	}
}

Word* heapPop() {
	if (hSize == 0) return 0;
	Word* ret = heap[1];
	heap[1] = heap[hSize--];
	int current = 1, leftChild = 2, rightChild = 3, child;

	while (leftChild <= hSize) {
		if (leftChild == hSize) child = leftChild;
		else child = (comp(heap[leftChild], heap[rightChild]) > 0) ? rightChild : leftChild;
		if (comp(heap[current], heap[child]) < 0) break;

		heapIDList[heap[current]->wID] = child;
		heapIDList[heap[child]->wID] = current;

		Word* tmp = heap[current];
		heap[current] = heap[child];
		heap[child] = tmp;

		current = child;
		leftChild = current * 2;
		rightChild = leftChild + 1;
	}
	return ret;
}

void update(int wID) {
	int current = heapIDList[wID];
	int parent = current / 2;
	heap[current]->count += 1;
	
	while (parent > 0) {
		if (comp(heap[current], heap[parent]) > 0) break;
		heapIDList[heap[current]->wID] = parent;
		heapIDList[heap[parent]->wID] = current;
		
		Word* tmp = heap[current];
		heap[current] = heap[parent];
		heap[parent] = tmp;

		current = parent;
		parent = current / 2;
	}
}

int isExist(const char* str, ull h) {
	Node* nd = hashTable[h].next;

	while (nd != 0) {
		if (!mystrcmp(wordList[nd->wID].str, str)) return nd->wID;
		nd = nd->next;
	}
	return 0;
}

int main() {
	char str[11];
	scanf("%d %d", &N, &maxLength);
	for (int id = 1; id <= N; id++) {
		scanf("%s", str);
		int length = mystrlen(str);
		if (length < maxLength) continue;

		ull h = hash(str);
		int checkID = isExist(str, h);
		if (checkID != 0) {
			update(checkID);
		}
		else {
			wordList[id].wID = id;
			mystrcpy(wordList[id].str, str);
			wordList[id].length = length;
			wordList[id].count = 1;
			heapPush(&wordList[id]);

			Node* nd = &nodePool[pcnt++];
			nd->wID = id;
			nd->next = hashTable[h].next;
			hashTable[h].next = nd;
		}
	}

	int loop = hSize;
	for (int i = 0; i < loop; i++) {
		printf("%s\n", heapPop()->str);
	}
	return 0;
}

 

확실히 Priority Queue(Heap)은 구현량이 많고 update 시켜 줘야 하면 heap에 어떻게 접근 할 것인지를 잘 생각해봐야 한다. (이번 문제는 단어의 고유 ID를 이용하고 각 힙 노드의 위치를 저장하는 heapIDList를 이용해 접근했다)

Hash Table은 문자열 탐색에 매우 적합하다.