[BOJ] 1620 나는야 포켓몬 마스터 이다솜

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

map

 

---------------------------------------------------풀이----------------------------------------------------

 

string을 입력받으면 number를, number를 입력받으면 string을 찾아 출력하는 문제이다.

hash를 구현하는 방법이 가장 빠르겠지만, stl을 사용해도 풀 수 있다. 따라서, map을 사용하였다.

string->number : map을 사용

number->string : array를 사용

number->string에 array를 사용하여 O(1)의 시간에 탐색이 가능하도록 하였다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <map>

using namespace std;

// name->number
map<string, int> m;
// number->name
string nums[100'001];

int str_to_int(string str){
    int num = 0;
    for(int i = 0; i < str.length(); i++){
        num = num*10 + str[i]-'0';
    }
    return num;
}

int main(void){
    FASTIO;
    int N, M;
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        cin >> nums[i];
        m[nums[i]] = i;
    }
    string tmp;
    for(int i = 0; i < M; i++){
        cin >> tmp;
        if('0' <= tmp[0] && tmp[0] <= '9'){
            cout << nums[str_to_int(tmp)] << "\n";
        }
        else{
            cout << m[tmp] << "\n";
        }
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

해시 함수를 구현하면 더 빠를 것 같은데, 귀찮아서 map으로 대체...

시간나면 해시 함수로 바꿔서 시간을 비교해야겠다.