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

문제: www.acmicpc.net/problem/1620

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

 

 

문제풀이

 

이분 탐색 문제이다.

 

포켓몬 이름이 입력으로 들어오면 포켓몬의 번호를, 포켓몬의 번호가 입력으로 들어오면 포켓몬의 이름을 출력해야 한다.

 

벡터를 두 개 선언해서 하나는 포켓몬 이름을 저장하고 다른 하나는 번호와 이름을 같이 저장한다.

번호와 이름을 같이 저장한 벡터는 sort() 함수를 이용해 사전 순으로 정렬해준다.

 

문제에 대한 입력을 받을 때 string 형으로 받는데 이 문자열의 첫째 자리가 65 미만이면(아스키코드)

번호가 들어온 것으로 인지하고 int 형 변환한 후 첫 번째 벡터에서 포켓몬 이름을 출력한다.

 

반대로 문자열의 첫째 자리가 65 이상이라면 포켓몬 이름이 입력된 것으로 두 번째 벡터에서 이분 탐색 후 해당 이름의 포켓몬 번호를 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare_func(pair<int, string> &p1, pair<int, string> &p2){ //사전순 정렬
    if(p1.second.compare(p2.second) > 0)
        return true;
    else
        return false;
}

int binary_search(vector<pair<int, string>> &v, string str){ //이분 탐색
    int start=0;
    int end=v.size()-1;
    
    while(start<=end){
        int mid = (start+end)/2;
        
        int comp = v[mid].second.compare(str);
        if(comp == 0){
            return v[mid].first;
        }
        else if(comp > 0){
            start = mid+1;
        }
        else{
            end = mid-1;
        }
    }
}

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

    int N, M;
    cin>>N>>M;

    vector<string> v1;
    vector<pair<int, string>> v2;
    for(int i=0; i<N; i++){
        string str;
        cin>>str;
        v1.push_back(str); //벡터를 두개로 저장한다.
        v2.push_back({i+1, str});
    }

    sort(v2.begin(), v2.end(), compare_func); //두번째 벡터만 사전순 정렬

    for(int i=0; i<M; i++){
        string str;
        cin>>str;
        
        if(str[0]<65){ //문자열 첫째자리가 65 미만이면 이름을 아니면 번호를 출력한다.
            cout<<v1[stoi(str)-1]<<"\n";
        }
        else{
            cout<<binary_search(v2, str)<<"\n";
        }
    }
    return 0;
}

 

 

결과

 

이 문제를 풀면서 배운 것이 있는데

벡터를 vector<pair<int, string>> 이 아닌 vector<pair<string, int>> 로 선언했다면

compare_func() 함수를 따로 정의할 필요 없이

sort() 함수가 알아서 사전 순 정렬을 해준다는 것입니다.