백준 1620 나는야 포켓몬 마스터 이다솜

많이 틀렸고, 시간을 단축시켰다. 시간 단축시킨 경험을 남기려고 글을 쓴다.

알고리즘 분류에 이분 탐색이라고 적혀있었고, 문제만 읽어봐도 숫자로 된 것은 직접적으로 찾아들어가 반환해주면 된다.
문제는 string으로 된 포켓몬 이름들을 찾아 들어가는 것이 문제였다. 정답 비율 보고 이건 순차적으로 찾으면 바로 퇴짜겠구나도 감이 올 것이고, 이분 탐색으로 푸는 것이 정당했다. 어찌 되었든 간에 이분 탐색이다!!!!!!!!
참고로 다른 사람들은 Map으로 푸는 것을 선호하는 것 같았다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(pair<int, string> a, pair<int, string> b){
    return a.second < b.second;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    int n, m;
    vector<pair<int, string>> pocketmonName;
    cin >> n >> m;
    string numbers[n];
    string temp;
    for(int i=1; i<=n; i++){
        cin >> temp;
        pocketmonName.push_back(make_pair(i, temp));
        numbers[i-1] = temp;
    }
    sort(pocketmonName.begin(), pocketmonName.end(), compare); // 포켓몬 이름으로 정렬
    for(int i=0; i<m; i++){
        cin >> temp;
        if(temp[0] >= '0' && temp[0] <= '9'){
            int t = stoi(temp);
            cout << numbers[t-1] << "\n";
        } else{
            int start = 0;
            int last = n-1;
            int mid;
            while(start <= last){
                mid = (start+last)/2;
                if(temp == pocketmonName[mid].second){
                    cout << pocketmonName[mid].first << "\n";
                    break;
                } else if(temp > pocketmonName[mid].second){
                    start = mid+1;
                } else{
                    last = mid-1;
                }
            }
        }
    }
}

벡터에 int, string 순으로 하고 compare 함수를 만들어 string 기준으로 정렬을 했다. 느렸다. 248ms가 나온 코드가 이거다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<pair<string, int>> pocketmonName;

int inputString(string &temp){
    int start = 0;
    int last = n-1;
    int mid;
    while(start <= last){
        mid = (start+last)/2;
        if(temp == pocketmonName[mid].first){
            return pocketmonName[mid].second;           
        } else if(temp > pocketmonName[mid].first){
            start = mid+1;
        } else{
            last = mid-1;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    cin >> n >> m;
    string numbers[n];
    string temp;
    for(int i=1; i<=n; i++){
        cin >> temp;
        pocketmonName.push_back(make_pair(temp, i));
        numbers[i-1] = temp;
    }
    sort(pocketmonName.begin(), pocketmonName.end()); // 포켓몬 이름으로 정렬
    for(int i=0; i<m; i++){
        cin >> temp;
        if(temp[0] >= '0' && temp[0] <= '9'){
            int t = stoi(temp);
            cout << numbers[t-1] << "\n";
        } else{
            cout << inputString(temp) << "\n";
        }
    }
}

벡터의 int , string 순서를 바꿔서 정렬했다. 속도는 128ms로 나왔다.
이 문제를 풀면서 신기했던 것은 문자를 비교할 때

이런 식으로 값이 크고 다른 것을 알 수 있다.< 문자열을 비교할 때 "사전에 먼저 나오면 작다"
그래서 else if(temp > pocketmonName[mid].first) 이런 식으로 비교가 가능하다.
또 하나 신기했던 것은 숫자와 문자를 받을 때 확인 방법이다.
숫자는 앞자리가 숫자면 숫자라

if(temp[0] >= '0' && temp[0] <= '9')
이런 식으로 확인하면 된다. 그리고 stoi로 문자 자체를 int로 바꿔 출력하면 된다.