[백준/c++] 19637 - IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

---

1) 풀이

STL에서 제공하는 lower_bound 함수를 사용하여 푸는 문제이다.

lower_bound 함수란, 간단히만 설명하자면 이진탐색 기반의 탐색 방법으로,

찾으려는 key 값보다 같거나 큰 숫자가 배열에서 몇번째로 처음 등장하는지 찾기 위해 사용하는 함수이다.

 

만약 찾는 key 값이 있으면 그 key값의 위치를, 없으면 key값보다 큰 가장 작은 정수 값의 위치를 반환한다.

이 함수는 탐색을 진행할 배열 혹은 벡터가 반드시 오름차순으로 정렬되어 있어야 사용할 수 있지만,

위 문제에서는 칭호가 전투력 상한값의 비내림차순으로 주어지기 때문에

즉 각 칭호의 전투력이 애초에 오름차순으로 주어지기 때문에 신경쓰지 않아도 된다.

lower_bound에 대한 자세한 설명과 사용방법에 대해서는 아래 3)참고자료 에 첨부

 

1. 칭호와 전투력을 각각 저장할 두개의 벡터를 만든다.
2. m개의 캐릭터 전투력을 전투력이 저장된 벡터에서 그 캐릭터의 전투력과 같거나 혹은 캐릭터의 전투력보다 큰 값 중 제일 작은 값의 인덱스를 찾는다.(lower_bound)
3. 그 인덱스를 이용해 칭호가 저장되어 있는 벡터에서 칭호를 출력한다. 

3의 보충 설명을 하지만, 칭호와 전투력은 함께 주어지고 그 짝에 맞게 각각의 벡터에 저장되었다.

즉, 다른 벡터지만 같은 위치에 저장되었기 때문에,

전투력이 저장된 벡터에서 반환된 인덱스를 칭호가 저장되어 있는 벡터에 대입하면 올바른 칭호가 나온다.

ex. 입력: WEAK 10000 / 칭호저장벡터[0]: WEAK , 전투력저장벡터[0]: 10000)

 

lower_bound 함수를 사용하면 쉬운 문제지만 인덱스를 구할 때, 유의할 점이 하나 있다.

lower_bound의 반환형은 iterator이므로 인덱스를 알고 싶다면 v.begin()을 빼주어야 한다.

(나는 벡터를 사용하였지만, 만약 배열인 경우 배열의 첫번째 주소를 가리키는 배열의 이름을 빼면 된다)

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
vector<string>s; //전투력 시스템 - 칭호 저장
vector<int>v; //전투력 시스템 - 전투력 저장
int n, m;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string tmp; //칭호
		int t; //전투력
		cin >> tmp >> t;
		s.push_back(tmp);
		v.push_back(t);

	}
	
	int find; //각 캐릭터의 전투력
	int idx; //해당 캐릭터에 알맞은 칭호의 위치(인덱스)
	for (int i = 0; i < m; i++) {
		cin >> find;
		idx = lower_bound(v.begin(), v.end(), find) - v.begin();
		cout << s[idx] << '\n';
	}
}

3) 참고자료

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

blockdmask.tistory.com/168