백준 1620번 c++ 풀이

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

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

사진이 너무 길어질까봐 오늘은 링크를 남깁니다.

안녕하세요 오늘은 이분탐색을 이용하여 문제를 풀어보겠습니다.

 

전략:

1. string타입의 vector와 int, string을 페어로 하는 pair타입의 vector를 선언해주고, input을 받아줍니다.

2. p를 정렬해줌으로 문자열 순서대로 정렬합니다.

3. 만약 들어오는 것이 index이면, v[index]를 출력하고, 그것이 아니면 이진탐색으로 pair vector에서 찾습니다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, M;
    cin>>N>>M;
    vector<string> v(N+1);
    vector<pair<string, int>> p(N+1);
    for(int i = 1; i<=N; ++i){
        string x;
        cin>>x;
        v[i] = x;
        p[i].first = x;
        p[i].second = i; 
    }
    sort(p.begin(), p.end());
    while(M--){
        string x;
        cin>>x;
        
        if(x[0] >='0' && x[0] <='9'){
            int num = 0;
            for(int i =0; i<x.length(); ++i){
                num += x[i] -'0';
                num *=10;
            }
            num/=10;
            cout<<v[num]<<"\n";
        }
        else{
          int low = 1, high = N;
          while(low<=high){
              int mid = (low + high)/2;
              if(p[mid].first == x){
                cout<<p[mid].second<<"\n";
                break;
              }
              if(p[mid].first<x){
                low = mid+1;
              }
              else{
                high = mid-1;
              }
          }
        }
    }
    return 0;
}