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

1. 문제 링크

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

2. 소스코드

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;
unordered_map<int, string> pokedex;
unordered_map<string,int> pokedex2;
int n, testcase, index;
string temp;
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> testcase;
	for (int i = 1; i <= n; i++) {
		cin >> temp;
		pokedex.insert({i,temp});
		pokedex2.insert({temp,i});
	}
	for (int i = 0; i < testcase; i++) {
		cin >> temp;
		if (temp[0] <= 57) {
			index = stoi(temp);
			cout << pokedex.find(index)->second << '\n';
		}
		else {
			cout << pokedex2.find(temp)->second << '\n';
			}
		}
	return 0;
}

3. 노트

3-1. 1년 전 첫 번째 츄라이

사실 문제 구현 자체는 그리 어렵지 않은데, 시간 제한을 통과하기가 은근히 까다로워 1년 전에 몇 번 시도하다가 묻어둔 문제이다.
1년 전에는 맵으로 {포켓몬 번호, 포켓몬 이름}을 저장하여, 숫자를 입력으로 받을 경우 해당하는 포켓몬의 이름을 O(1)로 출력하고, 문자를 입력으로 받을 경우 벡터를 이용하여 포켓몬 이름 순으로 맵을 따로 정렬한 후 이분탐색으로 해당하는 포켓몬의 번호를 출력하였다.

3-2. 때로는 연산 시간을 단축하기 위해 메모리를 투자하는 것도

map을 사용하면 O(1)의 시간에 찾는 자료에 접근할 수 있지만, 최대 100,000개의 입력이 주어지므로 주어진 입력을 하나의 map으로만 저장하고자 하였고, map을 두 개 쓰는 것은 생각조차도 못했다. (이래놓고 1차 시도에서 map 하나 두고, vector에 그거 복사한 건 뭐냥..)
이렇게 하면 이분탐색할 때는 시간초과가 나지 않지만, 정작 이분탐색을 위해 자료를 정렬할 때 시간초과가 나게 된다.
이를 해결하기 위해, 어차피 기존에 map 하나, vector 하나 둔 거랑 비슷하니, 아예 포켓몬 번호를 키값으로 하는 map 하나, 포켓몬 이름을 키값으로 하는 map 하나 총 두 개의 map을 생성하였고, 결과적으로 시간 초과도, 메모리 초과도 나지 않았다.