[백준][C++] 1620: 나는야 포켓몬 마스터 이다솜

문제 링크: https://www.acmicpc.net/problem/1620

 

이 문제를 푸는 방법은 여러가지가 있습니다.

• bidirectional map (양방향 맵)
• hash table (해시테이블)
• Trie (트라이)

그 중 양방향 맵으로 풀면 쉽습니다. key, value를 각각 이름, 번호로 하면 됩니다.

해시 테이블로 풀 때는 hash collision 처리를 잘 해주면 되겠습니다.

// 1620

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	map<string, int> m1;
	map<int, string> m2;

	int counter = 0;

	int n, m;
	cin >> n >> m;
	while (n--) {
		string s;
		cin >> s;

		++counter;
		m1.emplace(s, counter);
		m2.emplace(counter, s);
	}

	while (m--) {
		string s;
		cin >> s;
		
		if (isdigit(s[0])) {
			int num = stoi(s);
			cout << m2[num] << '\n';
		}
		else {
			cout << m1[s] << '\n';
		}
	}

	return 0;
}

c++에는 bimap을 쓰려면 boost::bimap을 쓰거나 std::map을 두개 쓰는식으로 해야합니다. 앞으로도 STL에 bimap이 추가될 가능성은 낮아 보이네요.