[Algorithm][C++] BOJ 1620: 나는야 포켓몬 마스터 이다솜 (Hash Table - Chaining (Single Linked List)

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

1620번: 나는야 포켓몬 마스터 이다솜

 

풀이 핵심

1. Hash Table을 이용해 포켓몬 이름(key)과 ID(value)를 저장한다. hash 값이 같을 경우 (충돌이 일어날 경우) 링크드 리스트로 연결지어 만든다. 다음과 같이 POKETMON 구조체와 hash 함수를 만든다.

#define HASH	5381

struct POKETMON {
	int id;
	char name[21];
	POKETMON* next;
};

ull hash(const char* str) {
	ull hash = HASH; // 해쉬 값은 소수이면서 2의 제곱수와 멀어야함
	int c;
	while (c = *str++) {
		hash = ((hash << 5) + hash + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

 

2. string 헤더의 strcmp, strcpy를 사용하거나 다음과 같이 직접 문자열을 복사하고 비교하는 함수를 구현해도 좋다.

그리고 입력이 index 값이 들어올 경우 (index 또한 문자열로 받을 것이므로) 문자열을 정수로 변환하는 함수도 구현한다.

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 stoi(const char* str) {
	int sum = 0;
	for (int i = 0; str[i]; i++) {
		sum *= 10;
		sum += (str[i] - '0');
	}
	return sum;
}

 

코드

#include <cstdio>
#define HASH		5381

// Hash Table의 크기는 소수이면서 클 수록 좋다
// 나중에 Hash Table의 크기를 변경하면서 최적화를 꼭 하자!
#define MAX_TABLE	10007

#define MAXN		100001
#define MAXM		100001
typedef unsigned long long ull;

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

POKETMON HASH_TABLE[MAX_TABLE];
POKETMON POOL[MAXN];
int pcnt;
POKETMON ARR[MAXM];

ull hash(const char* str) {
	ull hash = HASH;
	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 stoi(const char* str) {
	int sum = 0;
	for (int i = 0; str[i]; i++) {
		sum *= 10;
		sum += (str[i] - '0');
	}
	return sum;
}

int main() {
	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->id = i;
		mystrcpy(nd->name, str);

		nd->next = HASH_TABLE[h].next;
		HASH_TABLE[h].next = nd;
		mystrcpy(ARR[i].name, str);
	}
	for (int i = 0; i < M; i++) {
		scanf("%s", str);
		if (str[0] > '0' && str[0] <= '9') {
			int index = stoi(str);
			printf("%s\n", ARR[index].name);
		}
		else {
			ull h = hash(str);
			POKETMON* nd = HASH_TABLE[h].next;

			while (nd) {
				if (!mystrcmp(nd->name, str)) {
					printf("%d\n", nd->id);
					break;
				}
				nd = nd->next;
			}
		}
	}
	return 0;
}

 

ref: https://bloodstrawberry.tistory.com/