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

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

 

제출 코드

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

string ntoe[100001];
map<string, int> eton;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    string input;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> input;
        ntoe[i] = input;
        eton[input] = i;
    }

    while (m--)
    {
        cin >> input;
        if (isdigit(input[0]))
            cout << ntoe[stoi(input)] << '\n';
        else
            cout << eton[input] << '\n';
    }
}

map을 이용하면 string값으로 쉽게 숫자를 찾을 수 있지만, 반대로 value를 이용해 key를 찾으려면 시간이 많이 필요하기 때문에 숫자를 받아서 string을 찾을 수 있는 ntoe배열과 eton인 map 두 가지를 이용해 답을 찾아주었다

위 경우에는 map을 사용했는데, 최대 도감의 수가 100,000으로 큰 수이기 때문에 이 경우에는 unordered_map을 사용하면 시간 부분을 더 개선할 수 있다(단, 해시테이블로 구현한 자료구조이기 때문에 key가 유사한 데이터가 많을 경우 해시 충돌로 인해 성능이 오히려 떨어질 수도 있다)

* map의 시간복잡도: O(logn), unordered_map의 시간복잡도: O(1)

* 참고용. map -> unordered_map으로만 변경해서 제출한 결과다

(unordered_map의 헤더 파일은 unordered_map이다)