19637 - IF 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

생각해 보기

• 단순히 순차탐색의 경우 10^5 * 10*5으로 최악의 경우 시간초과가 발생한다.
• 이미 들어온 칭호 값의 경우 무시하고 넘어간다.
• 빠르게 값을 찾기 위해선 이분 탐색을 이용해야 한다.
• map의 lower_bound와 upper_bound를 이용하자.

코드

#include<iostream>
#include<map>

using namespace std;

map<int, string> titles;

int N,M;
void input(){
    string name;
    int power;

    cin>>N>>M;
    while(N--){
        cin>>name>>power;

        if(titles.find(power) != titles.end())
            continue;

        titles[power]=name;
    }
}

void solution(){
    int power;
    while(M--){
        cin>>power;

        auto it = titles.lower_bound(power);
        cout<<(*it).second<<'\n';
    }
}

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

    input();
    solution();

    return 0;
}