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

 

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

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

 

포켓몬 이름이 주어지고 입력되는 순서가 해당 포켓몬의 번호

M개의 알파벳이 입력되면 해당 번호 출력, 숫자가 입력되면 해당 포켓몬 이름 출력

 

 

☠️ 시행착오

 

1. map 사용하기 - {이름 : 번호}

    시간초과

2. 혹시나 하고 해 본, vector <pair> 사용하기

    시간초과

 

 

흠 시간 초과가 나는 이유가 뭘까?

일단, map의 경우 이름을 이용해서 번호를 찾는 것은 수월하다. key가 이름이기 때문에

map에서 Key를 이용해 value를 찾을 수 있다. (key를 인덱스로 사용해서 바로 접근 가능)

그런데 문제는, value를 이용해서 key를 찾는 것이다. 이렇게 되면 모든 key의 value를 확인해야 한다. 

여기서 시간이 오래 걸린다..!!

(vector<pair>의 경우도 똑같은 문제! - find함수로 모두 돌려보기...^^)

 

그러면.. 번호를 key로 사용하면 되지 않을까? 

배열은 인덱스를 int값으로 사용하기 때문에 적절할 거 같다

 

이름으로 번호를 찾을 땐, map을 사용해서 번호 값 출력하기

번호로 이름을 찾을 땐, arr를 인덱스 접근해서 이름값 출력하기 

 

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    map<string, int> ma;
    string name[100001];
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        string s;
        cin >> s;
        ma[s] = i;
        name[i] = s;
    }
    for(int i=1; i<=m; i++){
        string s;
        cin >> s;
        if(s[0] >= '1' && s[0] <= '9'){ //숫자
            cout << name[stoi(s)] << '\n';
        }else{
            cout << ma[s] << '\n';
        }
    }
    return 0;
}

//문자열을 key로 하는 ma  (map) -> value는 int
//숫자를 key로 하는 name (arr) -> value는 string