BOJ 9612 : Maximum Word Frequency

 

삼성 B형 전체 링크

 

www.acmicpc.net/problem/9612

 

 

해시 테이블을 이용하여 가장 빈도수가 높은 단어와 개수를 세보자.

같은 수의 단어가 있는 경우 사전 순으로 뒤에 있는 단어를 출력한다.

 

구조체에는 단어의 수와 실제 단어, 그리고 링크드 리스트를 위한 struct pointer가 필요하다.

메모리 풀 방식으로 연결하기 위해 POOL 메모리와 pcnt를 선언한다.

typedef unsigned long ul;

#define MAX_TABLE (1007)
#define MAX_WORD (20 + 5)

int N;

typedef struct st
{
	int count;
	char word[MAX_WORD];
	struct st *next;
}HASHTABLE;

HASHTABLE hashTable[MAX_TABLE];
HASHTABLE POOL[1000 + 50];
int pcnt;

 

문자열 copy 함수와 compare 함수, 그리고 hash 함수가 필요하다.

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

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

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

	return hash % MAX_TABLE;
}

 

main에서 입력을 받으면서 단어가 존재하면 수를 증가시키고, 존재하지 않으면 node를 연결한다.

for (int i = 0; i < N; i++)
{
	scanf("%s", input);

	if (isExist(input)) addCount(input);
	else addWord(input);
}

 

단어의 존재 여부는 word를 hash한 후에 hashTable[hash 값]의 링크드 리스트를 탐색하면 된다.

int isExist(char* word)
{
	ul h = hash(word);

	for (HASHTABLE *p = hashTable[h].next; p; p = p->next)
		if (mystrcmp(p->word, word) == 0) return 1;
	
	return 0;
}

 

단어의 수를 증가시키는 것은 isExist와 같은 방법으로 진행하면 되고, node의 count만 증가시킨다.

void addCount(char* word)
{
	ul h = hash(word);

	for (HASHTABLE *p = hashTable[h].next; p; p = p->next)
	{
		if (mystrcmp(p->word, word) == 0)
		{
			p->count++;
			return;
		}
	}
}

 

addWord는 hashTable[hash 값]에 연결만 하면 된다.

void addWord(char* word)
{
	ul h = hash(word);
	HASHTABLE *nd = &POOL[pcnt++];
	
	nd->count = 1;
	mystrcpy(nd->word, word);

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

 

실제 B형에서는 isExist, addCount, addWord를 하나의 함수로 통합하는 것이 좋다.

isExist에서 링크드 리스트를 탐색한 후 바로 count를 하면 되는데,

굳이 addCount에서 한 번 더 탐색할 필요는 없기 때문이다.

 

이 문제는 입력값이 작기 때문에 함수를 모두 분리하였다.

---

마지막으로 모든 hashTable을 탐색하면서 maxCount와 빈도수가 가장 큰 단어를 갱신한다.

빈도수가 같으면 answer와 p->word를 비교해서 작은 경우(answer가 사전 순으로 더 뒤인 경우)에 갱신한다.

int maxCount = 0;
char answer[MAX_WORD];
for (int i = 0; i < MAX_TABLE; i++)
{
	for (HASHTABLE *p = hashTable[i].next; p; p = p->next)
	{
		if (maxCount <= p->count)
		{
			if (maxCount == p->count && mystrcmp(answer, p->word) < 0) 
				mystrcpy(answer, p->word);
			else
			{
				maxCount = p->count;
				mystrcpy(answer, p->word);
			}
		}
	}
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

typedef unsigned long ul;

#define MAX_TABLE (1007)
#define MAX_WORD (20 + 5)

int N;

typedef struct st
{
	int count;
	char word[MAX_WORD];
	struct st *next;
}HASHTABLE;

HASHTABLE hashTable[MAX_TABLE];
HASHTABLE POOL[1000 + 50];
int pcnt;

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

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

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

	return hash % MAX_TABLE;
}

int isExist(char* word)
{
	ul h = hash(word);

	for (HASHTABLE *p = hashTable[h].next; p; p = p->next)
		if (mystrcmp(p->word, word) == 0) return 1;
	
	return 0;
}

void addCount(char* word)
{
	ul h = hash(word);

	for (HASHTABLE *p = hashTable[h].next; p; p = p->next)
	{
		if (mystrcmp(p->word, word) == 0)
		{
			p->count++;
			return;
		}
	}
}

void addWord(char* word)
{
	ul h = hash(word);
	HASHTABLE *nd = &POOL[pcnt++];
	
	nd->count = 1;
	mystrcpy(nd->word, word);

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

int main(void)
{
	char input[MAX_WORD];

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%s", input);

		if (isExist(input)) addCount(input);
		else addWord(input);
	}

	int maxCount = 0;
	char answer[MAX_WORD];
	for (int i = 0; i < MAX_TABLE; i++)
	{
		for (HASHTABLE *p = hashTable[i].next; p; p = p->next)
		{
			if (maxCount <= p->count)
			{
				if (maxCount == p->count && mystrcmp(answer, p->word) < 0) 
					mystrcpy(answer, p->word);
				else
				{
					maxCount = p->count;
					mystrcpy(answer, p->word);
				}
			}
		}
	}

	printf("%s %d\n", answer, maxCount);

	return 0;
}