백준 19637. IF문 좀 대신 써줘

백준 19637. IF문 좀 대신 써줘

이분탐색인데, 범위에 해당하는 문자열을 출력하는 문제

1. 간단 설명

---

칭호의 개수 N과 (1 <= N <= 100,000)

칭호를 출력해야 하는 캐릭터들의 개수 M (1<= M <= 100,000)

N개의 줄에 걸쳐 칭호의 이름 (1글자 이상, 11글자 이하의 영어 대문자로만 구성된 문자열)

칭호의 전투력 상한값을 나타내는 1,000,000,000 이하의 음이 아닌 정수가 주어짐

칭호는 전투력 상한값의 비내림차순으로 주어짐 (오름차순과는 다르지만 문제 풀이에는 크게 문제없음)

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력하기

2. 예제

---

3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000

3개의 칭호가 주어진다

0~10000만 사이는 WEAK, 10001~100000는 NORAML, 100001~1000000는 STRONG

이후 8명에 대해 알맞은 범위의 칭호를 출력하면 된다

0 -> WEAK
9999 -> WEAK
10000 -> WEAK
10001 -> NORMAL
50000 -> NORMAL
100000 -> NORMAL
500000 -> STRONG
1000000 -> STRONG

3. 알고리즘

---

먼저 브루트포스를 이용해 풀이한다면 다음과 같다

1. N, M 입력받기
2. 칭호와 전투력 상한값 저장 (vector< pair<string, int> > 를 이용)
3. M개의 캐릭터들에 대해 각각 검색 수행
	3-1. N개의 칭호에 대해서 이 칭호의 범위에 속하는지 체크
	3-2. 이 칭호 범위에 속한다면 (이전 칭호값보다 크고, 저장된 칭호값보다 작다면) 이를 출력

그러나 이 방법은 10만개의 칭호와

10만명의 캐릭터가 전투력이 모두 10억 때 최대 10만 x 10만 = 10^10번의 연산이 필요하다

1초에 약 10^8번 연산 가능하므로 시간초과 발생함

다른 방법 필요

이분탐색

이분 탐색은 정렬된 데이터에서 특정한 값을 빠르게 찾고 싶을 때”* 사용

이분탐색 문제의 특징들은 다음과 같다

1. 데이터를 정렬할 수 있음

2. 답이 하나의 범위 내에서 결정됨

3. 검색 대상이 매우 큼 (약 10억 이상)

이 문제는 칭호 목록이 전투력 상한 값 기준으로 정렬되어있고,

검색 대상이 매우 크므로 이분탐색을 적용하기 좋다

1. N, M 입력받기
2. 칭호 이름과 범위 입력받기
	2-1. 칭호, 상한값 쌍을 벡터에 저장
3. N개의 캐릭터들의 전투력을 입력받아 해당 캐릭터의 칭호 출력
	3-1. 각 캐릭터의 전투력에 대해 이분 탐색 수행

4. 소스코드

---

• 직접 만든 이분 탐색을 사용한 버전

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

using namespace std;

int N, M;
vector< pair<int, string> > titles;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;

	titles.resize(N);
	// 칭호와 이름 범위 입력 받기
	for (int i = 0; i < N; i++) {
		cin >> titles[i].second >> titles[i].first;
	}

	// 캐릭별로 칭호 출력

	for (int i = 0; i < M; i++) {
		int power; cin >> power;

		// 이분 탐색 
		int mid = 0;
		int l = 0, h = N - 1; // 인덱스
		int result = h;
		while (l <= h) {
			mid = (l + h) / 2;
			if (power <= titles[mid].first) {
				h = mid - 1;
				result = mid;
			}
			else {
				l = mid + 1;
			}
		}
		cout << titles[result].second << '\n';
	}

	return 0;
}

• algorithm 헤더의 lower_bound 사용 버전

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

using namespace std;

int N, M;
vector< pair<int, string> > titles;

struct Compare {
	bool operator()(const pair<int, string>& a, const pair<int, string>& b) {
		return a.first < b.first;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;

	titles.resize(N);
	// 칭호와 이름 범위 입력 받기
	for (int i = 0; i < N; i++) {
		cin >> titles[i].second >> titles[i].first;
	}

	// 캐릭별로 칭호 출력

	for (int i = 0; i < M; i++) {
		int power; cin >> power;
		auto it = lower_bound(titles.begin(), titles.end(), make_pair(power, ""), Compare());
		cout << it->second << '\n';
	}

	return 0;
}

lower_bound

• 찾으려는 key 값보다 같거나 큰 숫자가 배열에 몇번째에서 처음 등장하는지를 찾는 함수
• key 값보다 크거가 같은 숫자가 처음 나오는 위치의 인덱스를 반환함
• 탐색을 진행할 배열 혹은 벡터는 오름차순으로 정렬되어있어야 한다

upper_bound

• key값을 초과하는 숫자가 배열 몇번째에서 처음 등장하는지를 찾는 함수

• lower_bound와의 차이는 이상이냐 초과이냐 차이

• 람다식을 사용한 버전

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

using namespace std;

int N, M;
vector< pair<int, string> > titles;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;

	titles.resize(N);
	// 칭호와 이름 범위 입력 받기
	for (int i = 0; i < N; i++) {
		cin >> titles[i].second >> titles[i].first;
	}

	// 캐릭별로 칭호 출력

	for (int i = 0; i < M; i++) {
		int power; cin >> power;

		// 이분 탐색 
		auto it = lower_bound(titles.begin(), titles.end(), make_pair(power, ""),
			[](const pair<int, string>& a, const pair<int, string>& b) {
				return a.first < b.first;
			});

		cout << it->second << '\n';
	}

	return 0;
}