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

이 문제는 포켓몬 도감에 수록되어 있는 N개의 포켓못 정보를 가지고 M개의 질문이 들어왔을때 적절하게 결과를 반환해야 한다. 

우선 질문은 두가지로 다음과 같다.

1. 포켓몬 이름을 주어질 때 해당 포켓몬이 도감의 몇번째에 존재하는지

2. 숫자가 주어질때 해당 숫자의 포켓몬 이름은 무엇인지

 

도감에 수록된 포켓몬의 숫자 N는 100,000 이고 질문 M은 100,000 이므로 부르트포스 방법으로는 시간내에 문제를 해결할 수 없다. 따라서 해싱을 통해 O(1) 만에 탐색해야 한다.

 

숫자가 주어졌을 때 포켓몬 이름을 구하는 방법은 간단하게 배열의 인덱스를 활용하여 해결 가능하다. 하지만 포켓몬 이름이 주어졌을 경우 조금 생각을 해야한다.

 

만약 이름을 아스키 코드로 변환하여 그 값을 해시값으로 사용한다면 해시충돌이 발생할 가능성이 있다. 처음에는 이 해시 충돌을 피하기 위해 리스트 형식으로 구현하였지만 해시 충돌이 많을경우 결국 시간 복잡도는 최악의 경우 O(n)이 된다. 따라서 풀이 방법은 세가지로 다음과 같다.

 

1. 이진탐색을 통해한 풀이

2. 포켓몬 이름으로 직접 해시함수를 작성한 풀이

3. Map을 통한 풀이 

 

나는 이중에 3번째 방법으로 풀이하였다. 

#include<iostream>
#include<string>
#include<map>
using namespace std;

int n, m;
string poketmonName[100002];
map<string,int> poketmonList;

struct compare
{
	bool operator()(const pair<int, int>& value,
		const int& key)
	{
		return (value.first < key);
	}
	bool operator()(const int& key,
		const pair<int, int>& value)
	{
		return (key < value.first);
	}
};

void solution()
{
	for(int i = 0; i < m; i++)
	{
		string s;
		cin >> s;
		if(s[0] < 65)
		{
			int num = stoi(s);
			cout << poketmonName[num] << "\n";
		}
		else
		{
			cout << poketmonList[s] << "\n";
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for(int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		poketmonName[i] = s;//숫자로 물어봤을경우

		int hash = 0;
		for(int j = 0; j < s.size(); j++)
		{
			hash += s[j];
		}
		poketmonList.insert({ s,i });
	}

	solution();

}