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

문제 설명

먼저 포켓몬 도감'에 입력할 포켓몬 이름 리스트를 입력받는다,

이후 숫자를 입력하면 해당 도감 번호의 포켓몬 이름을 출력하고, 포켓몬 이름을 입력하면 도감 번호를 출력하는 문제이다.

접근

vector를 이용해서 도감을 구성하고, 이름을 입력받아 도감 번호를 출력할 때 find함수를 이용하면 시간 초과로 문제를 해결할 수 없다.

자료 검색에 걸리는 시간을 줄이기 위해 해시 테이블 자료 구조를 사용한다.

C++에서는 unnordered_map이라는 STL을 이용하면 된다. 자료 검색에 걸리는 시간복잡도가 O(1)이다.

 

unordered_map<int, string> m;

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

 

1번부터 N번까지 해시 테이블로 도감을 만든다. 

 

unordered_map<string, int> reversedMap;
for (const auto& p : m) {
    reversedMap[p.second] = p.first;
}

 

해시 테이블 m에서는 key - value 쌍을 도감 번호(int) - 포켓몬 이름(string)으로 해두었는데, 문제에서 요구하는대로 포켓몬 이름을 받아 도감 번호를 검색하려면 포켓몬 이름이 key가 되어야 한다.

 

메모리 크기는 2배로 소모하지만, 간단하게 key - value 쌍이 포켓몬 이름(string) - 도감 번호(int)인 reversedMap을 새로 만들었다.

 

for(int i = 0; i < M; i++) {
        string input;
        cin >> input;

        //입력한 문자열이 숫자인지 확인
        bool isNumber = true;
        for(char c : input) {
            if (!isdigit(c)) {
                isNumber = false;
                break;
            }
        }
        //숫자면 포켓몬 이름 출력
        if (isNumber) {
            cout << m[stoi(input)] << "\n";
        }
        //포켓몬 이름이면 숫자 출력
        else {
            cout << reversedMap[input] << "\n";
        }
    }

 

입력한 값이 숫자인지 문자열인지 판단한 후, 해당하는 map에서 value를 검색한다.

 

전체 코드

#include <iostream>
#include <unordered_map>

using namespace std;

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

    int N, M;
    cin >> N >> M;

    unordered_map<int, string> m;

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

    //key, value를 바꾼 reversedMap 생성
    unordered_map<string, int> reversedMap;
    for (const auto& p : m) {
        reversedMap[p.second] = p.first;
    }

    for(int i = 0; i < M; i++) {
        string input;
        cin >> input;

        //입력한 문자열이 숫자인지 확인
        bool isNumber = true;
        for(char c : input) {
            if (!isdigit(c)) {
                isNumber = false;
                break;
            }
        }
        //숫자면 포켓몬 이름 출력
        if (isNumber) {
            cout << m[stoi(input)] << "\n";
        }
        //포켓몬 이름이면 숫자 출력
        else {
            cout << reversedMap[input] << "\n";
        }
    }
}