[19637] IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

 

이분 탐색 문제다. 

 

칭호의 이름과 칭호에 맞는 전투력을 가지고 M개의 캐릭터에 맞는 칭호를 출력하면 되는 문제로, 캐릭터의 전투력이 어떤 칭호의 전투력의 범위 내에 있는지 확인하면 문제를 풀 수 있다. 범위를 두 번 체크할 필요는 없고 칭호를 비교할 때 작거나 같을 때만 어떤 칭호의 이름을 확인하면 된다.(이때 시간 복잡도는 M x log2N으로 10^8보다 작다.)

 

그래서 lower_bound를 사용해 현재 캐릭터의 전투력이 주어진 칭호보다 크거나 같을 경우 index를 구해 해당 index에 맞는 칭호의 이름을 출력하면 된다.

 

단, 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력해야 하므로 같은 전투력을 가진 칭호들 중 가장 먼저 입력된 칭호의 index을 얻는 코드가 추가적으로 필요하다.

 

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

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

	int N, M;
	vector<string> level;
	vector<int> power;

	cin >> N >> M;

	while (N--) {
		string a;
		int b;
		cin >> a >> b;

		level.push_back(a);
		power.push_back(b);
	}

	while (M--) {
		int character;
		cin >> character;

		// 캐릭터보다 전투력이 크거나 같은 레벨의 index
		int index = lower_bound(power.begin(), power.end(), character) - power.begin();

		// 전투력이 같은 레벨이 존재한다면, 그 레벨들 중 제일 왼쪽 index를 찾는다.
		while (index != 0 && power[index] == power[index - 1])
			index -= 1;

		cout << level[index] << "\n";
	}
}