BOJ 1620 : 나는야 포켓몬 마스터 이다솜 (Hash Table)

삼성 B형 전체 링크

 

www.acmicpc.net/problem/1620

 

참고

- 해시 테이블 Hash Table

- 해시 테이블 추가, 삭제, 수정, 검색

- 해시 응용 - 2차원 배열 탐색

- 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용)

- 해시 테이블 성능 비교

 

 

BOJ 1620은 실제 삼성 B형에서도 자주 나오는 문자열 해싱과 비슷해서 

Hash Table 연습 문제로 풀이를 만들어 보았다.

 

실제 B형에서 제공하는 hashing 함수를 이용해서 문제를 풀어보자.

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

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

	return hash % MAX_TABLE;
}

 

참고로 삼성 B형에서는 string 라이브러리를 사용할 수 없으므로 strcpy와 strcmp를 익혀두는게 좋다.

(가끔 코드를 제공할 때도 있다.)

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

 

먼저 POKETMON이라는 구조체를 정의하고, 포켓몬 도감 = HASH_TABLE을 만들자.

이때, MAX_TABLE은 10007이라는 소수로 만든다.

 

실제로는 N보다 큰 소수가 좋다.

Hash Table의 MAX_TABLE 관련 성능 비교는 링크를 참고하자.

#define MAX_TABLE (10007)

typedef struct st
{
	int index;
	char name[21];
	struct st *next;
}POKETMON;

POKETMON HASH_TABLE[MAX_TABLE]; /* 포켓몬 -> 숫자 */
POKETMON POOL[100000 + 5000];
int pcnt;

POKETMON ARR[100000 + 5000]; /* 숫자 -> 포켓몬 */

HASH_TABLE은 포켓몬이 입력되었을 때, 숫자를 출력해야 하고,

ARR는 숫자가 입력되었을 때, 포켓몬을 출력해야한다.

 

당연히 숫자가 입력되었을 때, 포켓몬을 출력하는 것은 배열이면 충분하다.

입력 받은 포켓몬 순서대로 ARR에 저장하고 숫자를 받으면 ARR[i].name 을 출력해주면 된다.

 

이제 Hash Table을 만들어 보자.

Hash Table은 Channing 방식으로 만들기 때문에 Linked List와 동일하다.

Key를 이용하여 head에 접근하는 것만 다르다.

 

Linked List의 Make 함수를 다시 한 번 보면, 아래와 같다.

void Make(int p, int c)
{
	NODE *nd = &POOL[pcnt++]; //노드를 하나 선언하고 MEMORY에서 당겨온다. 
	nd->node = c; //NODE에 값을 설정.

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

 

Linked List에서는 연결할 head를 p가 정해주었다.

여기서 p를 hash함수로 만들면 Linked List와 완전히 같게 된다.

 

이제 예시를 들어보자.

7개의 포켓몬이 들어오고 hash값은 아래와 같다고 가정하자. (실제론 다르게 나온다)

(2, 5번에서 충돌이 발생한다.)

 

1. Ivysaur        hash("Ivysaur") = 10004          
2. Pikachu       hash("Pikachu") = 3    
3. Bulbasaur    hash("Bulbasaur") = 5    
4. Butterfree    hash("Butterfree") = 507  
5. Raichu        hash("Raichu") = 3   
6. Rattata        hash("Rattata") = 508    
7. Caterpie      hash("Caterpie") = 10006   

 

4번까지 입력을 받으면 아래와 같은 Hash Table(Linked List)가 만들어 진다.

 

5번에서 충돌이 일어나므로, Linked List가 한칸씩 밀려나게 된다.

 

이제 Pikachu가 입력되었을 때, index 2를 어떻게 찾는지 보자.

ull h = hash("Picachu"); /* h = 3이 나오게 된다 */
POKETMON *nd = HASH_TABLE[h].next;

while (nd)
{
	if (!mystrcmp(nd->name, str)) /* nd의 name에서 Picachu가 있는지 체크 */
	{
		printf("%d\n", nd->index); /* 찾았으면 index 출력 후 종료 */
		break;
	}
    
	nd = nd->next; /* 못찾았으면 다음 node로 넘어간다. */
}

 

Hash Table에서는 충돌이 반드시 발생하기 때문에, key를 찾은 후,

key에 있는 모든 링크의 이름을 비교해서 index를 찾아야 한다.

 

물론, 입력 값이 적다면, 충돌이 없을 테니 key로 바로 접근할 수도 있지만,

B형의 경우 tc가 매우 크므로, 충돌을 반드시 고려할 수 밖에 없다.

 

최종 코드는 아래를 참고하자.

실제 B형에서는 init에서 HASH_TABLE을 모두 0으로 초기화 해야하는 코드를 추가해야 한다.

#include <stdio.h>

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

int N, M;
typedef struct st
{
	int index;
	char name[21];
	struct st *next;
}POKETMON;

POKETMON HASH_TABLE[MAX_TABLE];
POKETMON POOL[100000 + 5000];
int pcnt;

POKETMON ARR[100000 + 5000];

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

int change(char *str)
{
	int i, len;
	int sum, mul;

	sum = 0;
	mul = 1;

	for (i = 0; str[i]; i++);
	len = i;

	for (i = len - 1; i >= 0; i--)
	{
		sum += (str[i] - '0') * mul;
		mul *= 10;
	}

	return sum;
}

int main(void)
{
	char str[21];

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

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

		ull h = hash(str);
		POKETMON *nd = &POOL[pcnt++];

		nd->index = i;
		mystrcpy(nd->name, str);

		nd->next = HASH_TABLE[h].next;
		HASH_TABLE[h].next = nd; /* name에 해당하는 key에 연결 */

		mystrcpy(ARR[i].name, str); /* 순서대로 저장 */
	}

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

		if ('0' < str[0] && str[0] <= '9')
		{
			int index = change(str);

			printf("%s\n", ARR[index].name); /* ARR에 순서대로 저장했기 때문에 그대로 출력 */
		}
		else
		{
			ull h = hash(str);
			POKETMON *nd = HASH_TABLE[h].next;

			while (nd)
			{
				if (!mystrcmp(nd->name, str))
				{
					printf("%d\n", nd->index);
					break;
				}

				nd = nd->next;
			}
		}
	}

	return 0;
}

---

마지막으로 MAX_TABLE가 얼마가 적절한지에 대한 설명은 링크를 참고하자.

 

여기에서는 제대로 Hash Table이 만들어졌는지 확인하기 위해 많이 작은 값을 선택하였다.

 

참고로, Hash Table을 제대로 만들었다면, MAX_TABLE이 아주 작아도 성능만 느려질 뿐, 

memory crash가 나거나 하진 않는다. 

 

따라서 실제 시험에서는 MAX_TABLE을 바꿔가면서 memory crash가 나는지 확인하고, 

괜찮은 실행 시간 대의 값을 직접 찾아보면 된다.

---

어느 정도 구현이 가능하면 해시 테이블에서 데이터의 추가, 삭제, 수정을 공부해보자.