[BAEKJOON] 19637번 IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

문제조건

1. N개의 줄에 각 칭호의 이름과 칭호의 상한 값이 주어진다.
2. 칭호는 전투력 상한값의 비내림차순으로 주어진다. 
3. M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

처음 봤을때 너무 쉬워서 빠르게 구현부터했다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n, m;
vector<int> power;
vector<pair<string, int> > symbol;
int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		int up;
		cin >> s >> up;
		symbol.push_back(make_pair(s, up));

	}
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		power.push_back(a);
		for (auto up : symbol){
			if (up.second >= a) {
				cout << up.first << '\n';
				break;
			}
		}
	}
	
}

ㅋㅋㅋㅋ

그럼 그렇지 이렇게 쉽게 단순 구현으로 해결될 것이 아니었다.

문제를 다시 자세히 보니, 칭호의 개수와, 캐릭터의 개수가 각각 10^5이고, 내가 위에 짠 코드에서는 최악의 경우 10^5^5 까지 시간복잡도가 증가 할 수 있는데, 자그마치 100억이다 ㄷㄷ,,,, 1억번 연산당 1초가 걸리는데, 문제 제한조건인 1초보다 훨씬 많이 걸린다. 완탐 말고 시간 줄일 수 있는 좋은 알고리즘이 없나하는 찰나 비내림차순으로 정렬되어 전투력 상한값을 주어진다는 조건에서 이분탐색을 이용하는 방법을 떠올렸다. 

 

map에다 저장해놓고, 전투력 이상인 첫번째로 만나는 칭호를 출력하는 것이다.

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

이 글이 lower_bound에 대해서 자세히 설명해줬다. 많은 도움이 되었다. 따라서 이분탐색을 lower_bound로 간단하게 구현했다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n, m;
map<int, string> symbol;
int main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		int up;
		cin >> s >> up;
		symbol.insert({ up,s });
	}
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		auto iter = symbol.lower_bound(a);
		cout << iter->second << '\n';
	}
	
}