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

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

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

 

풀이

unordered_map을 이용한다. unordered_map은 hash_map c++ lib이다. 내부적으로 hash로 구현되어 있어 탐색하는데 O(1)의 복잡도를 가진다. 데이터가 최대 10만개를 가지고 최대 10만개의 문제가 주어지기 때문에 unordered_map을 사용해야 한다.

 

key를 통해 value로 접근하기 때문에

name으로 number를 접근하기 위한 unordered_map과

number으로 name를 접근하기 위한 unordered_map을 각각 만들어 접근한다.

 

주어진 문제에 대해서 isdigit을 통해 숫자인지 이름인지를 판단하고

숫자인 경우 stoi를 통해 숫자변환 후 find를 진행한다.

이름인 경우에는 key를 이름으로 하는 unordered_map에 바로 접근할 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cctype>

using namespace std;

unordered_map<string, int> list_name;
unordered_map<int, string> list_number;
vector<string> quiz;
int n, m;

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

    string str;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> str;
        list_name.insert({str, i});
        list_number.insert({i, str});
    }

    for (int i = 1; i <= m; i++){
        cin >> str;
        quiz.push_back(str);
    }

    for (int i = 0; i < m; i++){
        if(isdigit(quiz[i][0]) != 0){
            int num = stoi(quiz[i]);
            cout << list_number[num] << "\n";
        }else{
            cout << list_name[quiz[i]] << "\n";
        }
    }
}

 

배운 점

unordered_map : hash 기반의 map. crud O(1)를 가짐. 많은 데이터를 저장할때 사용.
stoi(string to integer) : string에 문자가 있으면 오류 발생. 문자열로된 순수 숫자로 이루어져있어야함.
atio() : c에서의 stoi. string타입을 지원하지 않기 때문에 str.c_str()로 변환하여 사용할 수 있음.
isdigit : string 전체가 아니라 인덱스 하나만 받아서 판별해준다.