[백준/c++] 20551 - Sort 마스터 배지훈의 후계자

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

20551번: Sort 마스터 배지훈의 후계자

---

1) 풀이

주어지는 input들을 하나의 벡터에 집어넣고, 정렬한 뒤 lower_bound 함수를 사용하여 찾고자 하는 값의 인덱스를 구한뒤 인덱스를 출력하면 되는 문제이다.

 

lower_bound 함수에 대한 설명은 최근에 풀이한 문제에 있으므로. 해당 글을 첨부해놓겠다🤗

2021.04.23 - [알고리즘 | 자료구조/백준] - [백준/c++] 19637 - IF문 좀 대신 써줘

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

lower_bound 함수를 이용해서 인덱스를 구한 후, 짚고 넘어가야 하는 것이 두가지 있다.

 

1. 반환된 인덱스의 자리에 찾고자 하는 값이 있는가?

2. 인덱스가 n(벡터의 길이) 미만인가?

 

lower_bound 함수는 벡터에서 찾고자 하는 값이 존재한다면 그 위치를 반환하지만,

만약 그 값이 존재하지 않는다면 그 이상의 값이 처음으로 나오는 위치의 인덱스를 반환한다.

그렇기 때문에 인덱스를 구하더라도, 벡터에서 그 인덱스 자리에 있는 값이 우리가 찾고자 하는 값인지 한 번 더 확인해주어야 한다. 만일 아니라면 -1 을 출력하면 된다.

 

또한, 벡터의 길이를 초과한 인덱스를 반환할 경우 에러가 발생하므로, 이 또한 코드에서 처리해주어야 한다.

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
vector<int>v; //문제에서의 배열 A
int n, m;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) { //n개의 원소 저장
		int t;
		cin >> t;
		v.push_back(t);
	}
	sort(v.begin(), v.end()); 
	for (int i = 0; i < m; i++) {
		int d;
		cin >> d;
		int idx = lower_bound(v.begin(), v.end(), d) - v.begin(); //찾고자 하는 값의 인덱스
		if (idx >= n || v[idx] != d) cout << -1 << '\n';
		else cout << idx << '\n';
	}

}

3) 참고자료