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

이분탐색을 이용한 문제이다~ 

 

#접근방법 

 

이분탐색을 떠올려야 하는 단골 조건은 조건 범위가 10억을 넘길때이다.  

뭐 아닌 문제도 있긴하겠지만 이분탐색을 이용해서 풀어야하는 문제는 대부분 10억 정도 되는 값을 조건으로 주어지기 때문에 해당 조건을 만났을 때 이분탐색을 의심해봐야한다. 

 

이번 문제도 마찬가지다. 아래 조건을 보고 이분탐색을 고려해봐야한다. 

 

칭호의 개수 N (1 ≤ N ≤ 10^5)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 10^5)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 10^5)

 

칭호의 개수가 100000 (10만) 이다. 그리고 캐릭터들의 개수 또한 100000 (10만) 이다. 

그럼 여기서 생각을 해야할 것이 10만개의 캐릭터가 모두 상한값을 가지고 있다고 치고, 각 캐릭터마다 반복문을 돌면서 조건에 부합되는지 확인해야한다. 

 

즉, 그냥 이중 for문을 이용해서 조건이 맞는지 판별했을 때 최악의 상황일 때는 10만 X 10만 = 100억이라는 연산이 걸린다. 

 

그래서 해당 문제는 이분 탐색을 이용해서 풀어야한다. 

문제의 조건에서 

 

칭호는 전투력 상한값의 비내림차순으로 주어진다.

 

즉, 오름차순으로 주어지기 때문에 이분탐색을 위한 셋팅은 입력값으로만으로도 해결된다. 

그리고 이분탐색 알고리즘을 통해서 해당 문제를 해결하자. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std; 

int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	int a, b; cin >> a >> b; 
	vector <pair <int, string>> v(a);
	for (int i = 0; i < a; i++) cin >> v[i].second >> v[i].first; 
	for (int i = 0; i < b; i++) {
		int x; cin >> x; 
		int l = 0; 
		int h = v.size() - 1;
		int result = h; 
		while (l <= h) {
			int mid = (l + h) / 2; 
			if (v[mid].first >= x) {
				h = mid - 1; 
				result = mid; 
			}
			else l = mid + 1; 			
		}
		cout << v[result].second << "\n"; 
	}
}

19637번: IF문 좀 대신 써줘