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

문제

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

19637번: IF문 좀 대신 써줘

 

해결방법

1. 특정 값이 아닌 범위를 찾는 것임을 기억하고 있어야 한다.
2. 출력할 수 있는 칭호가 여러 개일 경우 가장 먼저 입력된 칭호 출력해야 하므로 입력받은 값 X가 mid번째 칭호의 전투력보다 작거나 같으면(x < v[mid].second) right=mid-1을 해준다. 이 외에는 left=mid+1을 해준다.
3. 위에서 X와 칭호의 전투가 같았을 때에도 mid-1을 해주기 때문에, 이분탐색 이후에 X가 mid번째 칭호의 진투력보다 크다면 mid+1번째 칭호를 출력한다.  

 

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

	int n, m;
	cin >> n >> m;
	vector<pair<string, int>>v;
	string str;
	int x;

	for (int i = 0; i < n; i++) {
		cin >> str >> x;
		v.push_back({ str, x });
	}

	for (int i = 0; i < m; i++) {
		cin >> x;

		int left = 0, right = n - 1, mid = (left + right) / 2;
		while (left <= right) {
			mid = (left + right) / 2;

			if (x <= v[mid].second) 
				right = mid - 1;
			else
				left = mid + 1;
		}

		if (x > v[mid].second) { 
			cout << v[mid + 1].first << '\n';
		}
		else
			cout << v[mid].first << '\n';
	}

	return 0;

}