[백준(BOJ)] IF문 좀 대신 써줘(19637번)_C++

문제를 보고 가장 먼저 떠오른 생각은 그냥 브루트포스로 모든 경우를 확인하는 방법이었다.

그러면 시간복잡도는 O(nm)이 되므로 시간 제한을 초과할 수 밖에 없다.

 

이때는 간단하게 이분탐색을 사용하면 된다.

대신 칭호에 대한 상한전투력을 기준으로 이분탐색을 진행하면 안된다.

칭호에 대한 상한전투력은 연속된 수가 아니고, 구간이므로 정확한 구간을 판단할 수 없다.

따라서 칭호에 대한 인덱스를 기준으로 이분탐색을 수행해야 한다.

 

---

정답 코드

#include <iostream>

using namespace std;

int n, m, score;
pair<string, int> title[100000];

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

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

        int l = 0;
        int r = n - 1;
        while (l < r){
            int mid = (l + r) / 2;

            if (score <= title[mid].second)
                r = mid;
            else if (score > title[mid].second)
                l = mid + 1;
        }

        cout << title[l].first << "\n";
    }

}