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

1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net)

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

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 

문제가 백준 역대급으로 길어서 중간 부분만 짤라왔으니,,, 본문은 주소에 들어가서 확인하면 될 것 같다.

 

문제 자체는 간단하다.

 

포켓몬 이름을 순서대로 입력 받으면, 그 순서가 곧 도감 번호가 되어 기록되어야 한다는 것이다.

 

나중에 출력은 포켓몬 이름을 물으면 도감 번호를, 도감 번호를 물으면 포켓몬 이름을 뱉어야 한다.

 

복잡한 알고리즘 필요없이, 그냥 도감 번호를 기준으로 정렬된 벡터와 포켓몬 이름으로 정렬된 벡터를 선언하여 문제를 해결했다.

 

사용한 알고리즘 방식은 다음과 같다.

 

1. 입력받을 때, (도감번호 , 포켓몬) 의 pair 값을 vector에 때려박는다.

2. 만약 들어온 테스트 입력 값이 포켓몬이라면, 포켓몬 이름으로 정렬된 벡터에 접근한다.

3. 이진 탐색을 통해 돌아가면서, 만약 포켓몬 이름이 second에 값에 찾아진다면, first 값에 접근한다 (도감 번호)

4. 만약 들어온 테스트 입력 값이 도감번호 라면, 그냥 도감번호에 접근해 그 second 값을 뱉으면 된다!

 

다음은 그걸 해결한 C++ 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cctype>

using namespace std;
bool cmp (pair<int, string> a, pair<int, string> b){
    return a.second < b.second;
} 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<pair<int, string>> dogam;
    string info;
    getline(cin,info);
    int total, mine;
    istringstream ss(info);
    ss >> total >> mine;
    vector<pair<int, string>> copy;
    for (int i=0;i<total;i++){
        string poketmon;
        cin >> poketmon;
        dogam.push_back(make_pair(i, poketmon));
        copy.push_back(make_pair(i, poketmon));
    }
    sort(dogam.begin(),dogam.end(),cmp);
    sort(copy.begin(),copy.end());
    for (int i=0;i<mine;i++){
        string test;
        cin >> test;
        if (isdigit(test[0]) == 0) {
            unsigned int start = 0;
            unsigned int end = total-1;
            unsigned int mid = 0;
            while (start <= end){
                mid = (start+end)/2;
                if (dogam[mid].second == test) break;
                else if (dogam[mid].second > test) end = mid - 1;
                else start = mid + 1;
            }
            cout << dogam[mid].first+1 << '\n';
        }
        else {
            cout << copy[stoi(test)-1].second << '\n';
        }
    }

    return 0;
}