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

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

풀이

포켓몬의 이름(string)과 번호(int)를 어떻게 함께 저장하고, 탐색할 것인지가 중요한 문제였다.

입력으로 문자열이 들어올 경우, 번호를 출력해야 하는데, 포켓몬의 이름은 중복이 없기 때문에 map<string, int>에 (이름, 번호) 쌍을 저장하였다.

반면 입력으로 숫자가 들어올 경우, 이름을 출력해야 하는데, 만들어둔 map에서 value로 key를 찾는 것은 비효율적이므로(선형 스캔으로 비교해야 함) string 배열을 만들어서 (번호, 이름) 쌍을 인덱스와 값으로 저장하였다.
포켓몬 번호는 중복이 없고, 입력받는 순서대로 증가하므로 인덱스로 사용하기에 적합하다. 문자열을 입력받을 때처럼 map을 사용할 수도 있겠지만, 삽입 및 검색에 시간이 많이 걸린다. vector의 경우 삽입과 검색에 O(1), map의 경우 삽입과 검색에 O(logN) 시간이 필요하기 때문이다.

코드

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;

    map<string, int> m;
    vector<string> v(N+1);
    string s;
    for(int i=1; i<=N; i++) {
        cin >> s;
        m.insert({s, i});
        v[i] = s;
    }

    while(M--) {
        cin >> s;
        if(s[0] > '0' && s[0] <= '9') {
            int num = stoi(s);
            cout << v[num] << "\n";
        } else cout << m[s] << "\n";
    }

    return 0;
}