[백준,c++] 19637번 - IF문 좀 대신 써줘

문제

19637번: IF문 좀 대신 써줘

 

코드

#include <iostream>
#include <map>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M; cin>>N>>M;
    multimap<int, string> m;
    for(int i=0; i<N; i++){
        string a; int b;
        cin>>a>>b;
        m.insert({b,a});
    }
    
    for(int i=0; i<M; i++){
        int inp; cin>>inp;
        cout<< (m.lower_bound(inp)) ->second <<'\n';
    }
    
}

 

풀이

해당 주어지는 입력값이 어느 범위에 속하는지 출력하는 문제입니다. 

10^5까지 입력이 들어오기에 O(N^2)으로 풀면 시간 안에 해결할 수 없어 binary search를 사용하여 풀어야 합니다.

저는 map을 이용해서 해결했습니다.

1. key를 전투력 상한 값, value를 칭호로 하여 multimap을 정의합니다.
2. multimap을 사용 한 이유는 예제 입력 2번에서 동일한 상한 값이 들어오는 경우가 있기 때문입니다.
3. unordered_map의 경우는 hash로 구현되어 있지만 일반 map과 multimap은 레드 블랙 트리로 구현되어 있어서 binarysearch 메서드를 제공합니다.
4. lower_bound를 사용하면 해당 입력값보다 처음으로 같거나 높은 값의 칭호를 출력할 수 있습니다.