백준 1620 나는야 포켓몬 마스터 이다솜 c++ [컴공과고씨]

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

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

이 문제의 경우 시간초과를 잘 통과해야하는 문제이다.

그러기 위해서는 해시맵을 사용해야하며 문제를 보면 번호를 주면 포켓몬 이름을 포켓몬 이름을 주면 도감 번호를 답해야한다. 하지만 해시맵은 Key, value가 있고 key값으로 value를 찾는건 빠르지만(포켓몬 이름(key)을 주었을 때 도감 번호(value)를 찾는) value(도감번호)로 key(포켓몬 이름) 값을 찾으려면 iter를 이용해서 하나하나 같은지 체크하면서 구해주어야 하므로 시간이 오래걸린다. 그래서 이 부분은 해시맵에서 해결하는 것이 아니라 배열에 포켓몬 이름을 저장해주어

도감 번호를 배열에 넣기만해도 답을 구할 수 있도록 구현하였다. 

문제 풀이

1.  해시 맵에 key값에는 포켓몬 이름 value 값에는 도감 번호를 저장해주고 name배열을 만들어 포켓몬 이름을 도감 번호대로 저장해준다. 이 때 입력값을 string으로 받아준다.

 

2. 문제에서 포켓몬의 이름이 주어질때는 맨 앞 문자는 무조건 대문자이므로 앞문자가 'A'에서 'Z'사이에 있다면 포켓몬 이름이 주어진 것으로 해시맵에 넣어 도감번호를 얻어준다. (아스키 코드로 A = 65, Z=90 물론 그냥 'A', 'Z'로 써도됨)

 만약 'A' 와 'Z'사이에 없다면 번호가 주어진 것이므로 name배열에 넣어주면 된다. 주의할 것은 string으로 값을 받아왔기 때문에 stoi를 이용하여 정수로 변환 후 name[stoi(얻은값)] 이렇게 해주어야한다.

 

3. 얻은 답을 result 벡터에 넣어주어 출력해주면 된다. 

 

 

전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
//해시맵사용
int main(){
    map<string, int> pokemon;
    vector<string> name;
    int n, m;
    string temp; //포켓몬 이름과 번호가 섞여있으므로 string
    cin >> n >> m;
    vector<string> result; 
    for (int i = 1; i <= n;i++){
        cin >> temp; 
        name.push_back(temp); // 도감번호 주어질때 포켓몬 이름 찾기
        pokemon.insert(make_pair(temp, i)); // 포켓몬 이름이 주어질때 도감번호 빠르게 찾기
    }
    for (int i = 0; i < m; i++){
        cin >> temp;       
        if(temp[0] >= 65 && temp[0] <= 90){ 
        // 포켓몬 이름이 주어진 경우 (맨 앞 문자가 영어 대문자인것을 이용)
            result.push_back(to_string(pokemon[temp]));
            //result 벡터는 string이기 때문에 번호를 string으로 변환해줌
        }
        else // 도감 번호가 주어진 경우
        {
            result.push_back(name[stoi(temp)-1]);
            //입력값은 string 그래서 정수형으로 변환 후 넣어줌
            // -1을 해준 이유는 name배열은 0부터 시작했기 때문 
        }
    }
    for (int i = 0; i < result.size();i++){
        cout << result[i] << '\n'; // 출력
    }
    return 0;
}

사용 알고리즘 : 해시맵(hash map)

 

yea!