[백준/c++] 19637번: IF문 좀 대신 써줘

 

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

19637번: IF문 좀 대신 써줘

 

예를 들어,

10,000 <= 전투력 : WEAK,

10,000 < 전투력 <= 100,000 : NORMAL,

100,000 < 전투력 <= 1,000,000 : STRONG

 

전투력에 맞는 칭호를 출력하는 프로그램 작성하자.

 

#include <iostream>
using namespace std;
string answer;
int n, m;
int value[100000];    //전투력 기준
string title[100000]; //칭호

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> title[i] >> value[i];
    for(int i=0; i<m; i++){
        int k;
        cin >> k;
        cout << title[binarySearch(k)] << '\n';
    }
    return 0;
}

 

그냥 for문으로 하면 시간 초과된다..

이분 탐색으로 하면 된다..

 

칭호 n개를 left = 0, right = n-1로 정하고 중앙 mid를 value 값 인덱스로 해서 이분 탐색을 진행한다.

탐색 후, value [mid] 값이 k보다 크면 mid 인덱스를 한 번 증가시키고 아니라면 mid를 출력해서 title 배열 값을 출력한다.