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

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

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

 

해결방법

 

    unordered_map을 통해 쉽게 해결했다.

그냥 map 을 사용하면 해결이 되지 않는다. 왜냐하면 value를 통해 key 를 찾는 과정에서 결국에는 N번만큼의 선형 탐색을 하게 되기 때문이다. 따라서 시간 초과가 뜬다. 처음엔 나도 왜 시간 초과가 뜨나 했지만 map 이 이진탐색트리로 구현되어 삽입 시 자동정렬 된다는 사실을 망각하였었고, 이름만 map이고 정렬이 되지 않는 해시 자료구조인 unordered_map 을 사용하여 탐색 시간복잡도를 O(1)로 맞출 수 있었다. 하지만 메모리 공간이 두배로 필요했다.

 

unordered_map <string, int> m;
unordered_map <int,string> m_reverse; 

 

이렇게 두 배의 공간이다. 

 

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map <string, int> m;

unordered_map <int,string> m_reverse; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;


    cin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        string input;

        cin >> input;

        m.insert({ input,i});
        m_reverse.insert({ i,input });
    }

    for (int i = 1; i <= M; i++)
    {
        string input;

        cin >> input;

        unordered_map<string, int>::iterator iter;

        if (input[0] <= 'Z' && input[0] >= 'A')
        {
            cout << m.at(input) << '\n';
        }
        else
        {
            cout << m_reverse.at(stoi(input)) << '\n';
        }
  
    }


    return 0;
}