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

나는야 포켓몬 마스터 이다솜 (실버 4)

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

 문제가 너무 길어서 링크에서 참조해주세요

 

 

입력받는 포켓몬 개수 N, 맞춰야하는 문제 M 이 주어집니다.

포켓몬은 1번부터 번호 순서대로 입력됩니다.

 

---

풀이

입력받고 {번호, 포켓몬이름} 의 구조체로 저장한 뒤, 

번호를 입력받으면 이름을, 이름을 입력받으면 번호를 찾아서 출력하면 되는 문제입니다.

 

논리적으로는 간단하지만, 제한 시간이 짧아서 

반복문을 통한 비교를 하면 바로 시간제한이 뜹니다.

 

map 등의 자료구조를 통한 탐색을 해야 합니다.

 

여기서 vector 또는 배열 사용 후 for 문으로 탐색 시 시간복잡도는 

O(n)

 

map 의 시간 복잡도는

O(logN)

 

unordered_map 의 시간복잡도는 

O(1) 

 

이 문제의 경우 정렬을 따로 쓰지 않으니, unordered_map을 사용하면 성능이 더 빨라집니다.

 

같은 코드로 map 과 unordered_map 사용을 비교해보니 백준 채점 기준

각각 200ms / 120ms 정도로 상당히 차이가 많이 나는것을 확인가능합니다.

 

map/ unordered_map  구조체의 경우 키 값을 string 으로도 설정할 수 있어서,

key 가 번호인 구조체랑 key 가 포켓몬 이름인 구조체 2개를 선언했습니다.

unordered_map<int, string> pkmon;
unordered_map<string, int> pkmonByName;

 

번호를 입력받은 경우  와   포켓몬 이름을 입력받은 경우 를 구분해서 처리해야 하는데,

포켓몬 이름은 알파벳으로 구성되었다고 언급되므로 입력은 string 으로 받은 후 isalpha()를 통해 첫번째 글자가 알파벳인지 확인했습니다.

        string str;
        cin >> str;

        // 이름을 받은경우
        if (isalpha(str[0]))
        {
            int num = findPocketMonNum(str);
            cout << num +1 << "\n";
        }

 

번호 = 인덱스 + 1 이므로 번호를 입력받은 경우 는 바로 출력하면 되고,

포켓몬 이름을 입력받은 경우 는 find() 함수를 통해 탐색해야합니다.

int findPocketMonNum(string pkname)
{
    if (pkmonByName.find(pkname)!= pkmonByName.end())
    {
        return pkmonByName[pkname];
    }
}

---

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
using namespace std;
using std::cin;

unordered_map<int, string> pkmon;
unordered_map<string, int> pkmonByName;

int findPocketMonNum(string pkname)
{
    if (pkmonByName.find(pkname)!= pkmonByName.end())
    {
        return pkmonByName[pkname];
    }
}

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

    int n;
    int k;

    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        string name;
        cin >> name;

        pkmon.insert(make_pair(i, name));
        pkmonByName.insert(make_pair(name, i));
    }

    // 출력시작
    for (int i = 0; i < k; i++)
    {
        string str;
        cin >> str;

        // 이름을 받은경우
        if (isalpha(str[0]))
        {
            int num = findPocketMonNum(str);
            cout << num +1 << "\n";
        }
        // 번호를 받은 경우
        else
        {
            int intnum = stoi(str);
            cout << pkmon[intnum -1] << "\n";
        }
    }
}