[백준/BOJ] 1620번 나는야 포켓몬 마스터 이다솜 (C/C++)

백준 온라인 저지(BOJ) 1620번 나는야 포켓몬 마스터 이다솜
https://www.acmicpc.net/problem/1620

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

* 사용언어 : C언어, C++
 

1. 문제

N개의 줄에 1부터 N번까지의 포켓몬 이름이 주어짐
이후 M개의 줄에 이름 or 번호가 주어졌을 때 해당되는 번호 or 이름을 출력

 

2. 풀이

문제 설명이 상당히 길고 장황해서 의아했습니다.
백준 문제를 풀다보면 문제를 해결하는 것과 무관한 내용이 가득 적혀있을 때가 종종 있는 것 같습니다.
구체화되지 않은 고객의 요구사항을 해석하는 능력을 길러보았다고 생각했습니다. (억지 의미부여)
 
문제를 요약해보자면,
1부터 N까지 순서대로 주어진 N개의 이름을 mapping하여 저장한 후에
M개의 입력을 받아 mapping 되는 정보를 출력하면 됩니다. (이름 ↔ 번호)
 
 
저는 아래 2가지 자료구조를 사용하여 문제를 풀었습니다.
1) 번호 → 이름 : 문자열 array
2) 이름 → 번호 : hash table
 
왠지 하나의 자료 구조로 풀 수 있을 것 같은 느낌이 들었지만,
고민해도 답이 나오지 않아서 그냥 2개의 자료 구조를 각각 구현하여 풀었습니다.
 
M개의 입력을 받을 때는 일단 문자열(s)로 받습니다.
입력의 첫 번째 글자(s[0])가 숫자(번호)이면 index로 문자열 array를 탐색하여 저장된 이름을 출력했고
문자(이름)이면 hash find를 하여 struct에 저장한 번호를 출력했습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1620_나는야 포켓몬 마스터 이다솜
11368KB	120ms
*/
#include <cstdio>

const int LM = 100001;
const int HLM = LM * 3;
const int CLM = 21;

struct _ht {
	char key[CLM];
	int value;
} ht[HLM];

char a[LM][CLM];
int N, M;

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

void my_strcpy(const char* src, char* des) {
	while (*src) *des++ = *src++;
	*des = 0;
}

int hash(const char *s) {
	unsigned long hash = 5381;
	int c;
	while (c = *s++) hash = (((hash << 5) + hash) + c) % HLM;
	return hash % HLM;
}

int h_add(const char *name, int num) {
	int h = hash(name);

	while (ht[h].key[0]) h = (h + 1) % HLM;
	my_strcpy(name, ht[h].key);
	ht[h].value = num;
	return 1;
}

int h_find(const char * name) {
	int h = hash(name);
	int cnt = HLM;

	while (ht[h].key[0] && cnt--) {
		if (!my_strcmp(name, ht[h].key)) return ht[h].value;
		h = (h + 1) % HLM;
	}
	return -1;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	char s[CLM];
	int n, j;

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

	for (int i = 1; i <= N; ++i) {
		scanf("%s", s);
		h_add(s, i);
		my_strcpy(s, a[i]);
	}

	for (int i = 0; i < M; ++i) {
		scanf("%s", s);
		if (s[0] > '0' && s[0] <= '9') {
			n = 0, j = 0;
			while (s[j]) n = n * 10 + s[j++] - '0';
			printf("%s\n", a[n]);
		}
		else printf("%d\n", h_find(s));
	}
	return 0;
}