Baekjoon 19637번 IF문 좀 대신 써줘

문제

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

걸린 시간

01 : 42 : 43

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, m;
int power[100000];
string title[100000];

int binsearch(int p){
    int mid = 0, left = 0, right = n-1;
    while(left <= right){
        mid = (left+right)/2;
        if(p <= power[mid])
            right = mid-1;
        else
            left = mid+1;
    }
    if(p > power[mid])
        return mid+1;
    else
        return mid;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> title[i] >> power[i];
    int p;
    for(int i = 0; i < m; i++){
        cin >> p;
        cout << title[binsearch(p)] << "\n";
    }
    return 0;
}

중첩 if 문을 사용할 경우 복잡도는 O(MN) 으로 시간초과가 난다.

이분탐색을 이용하면 O(MlogN) 까지 줄일 수 있을 것 같다.

칭호의 전투력은 비내림차순으로 주어지는데 문제에서 주어진 예시처럼 if 문을 작성하다고 하면, 같은 전투력의 다른 칭호는 먼저 입력된 칭호에 의해 분기되어 사용되어지지 않는다.

직접 이분 탐색을 구현한다면 이를 유의하여야 하고 라이브러리를 사용할 경우 lower_bound 함수를 사용해야 한다.