백준 19637 IF문 좀 대신 써줘

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

 

 

문제에서의 if문을 그대로 사용하게 되면 시간초과가 발생한다.

이를 개선하기 위해 binary search 알고리즘을 사용하여 해결했다.

 

입력된 power가 들어오면 이게 어느 경계 전투력에 포함되는지 확인한다.

그 후 mid의 칭호를 쓸지 다음의 칭호를 쓸지 확인한다.

 

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

using namespace std;



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n >> m;

    vector<pair<string, int>> grade(n);


    for (int i = 0; i < n; i++) {
        cin >> grade[i].first >> grade[i].second;


    }





    for (int i = 0; i < m; i++) {

        int power;

        cin >> power;

        int start = 0;
        int end = n - 1;
        int mid;

        while (start <= end) {
            mid = (start + end) / 2;

            if (power > grade[mid].second) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        //mid의 경계선에서 다음 칭호를 받을 지 이전 칭호를 받을 지 선택
        if (power > grade[mid].second) {
            cout << grade[mid+1].first << "\n";
        } else {
            cout << grade[mid].first << "\n";
        }



    }





    return 0;
}

 

 

 

ps) 이분탐색을 너무 얕봤다고 생각한다. 단순한 검색 알고리즘이라고 생각했다가 아주 살짝만 비틀었는데 실버3에서도 애를 먹는 나 자신을 발견할 수 있었다. 지금까지 알고리즘을 하루에 한번씩 돌아가며 문제를 풀었지만 그 과정에서 내가 약한 알고리즘을 깨달을 수 있었으니 이를 감안해서 나의 약점 위주로 다시 풀어봐야겠다.