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

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

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

문제

지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 N$N$개의 원소를 가진 배열A$A$를 주고, A$A$의 원소들이 오름차순으로 정렬된 배열B$B$를 만들게 한다. 그다음 M$M$개의 질문을 한다. 각 질문에는 정수 D$D$가 주어진다. 제자들은 주어진 정수D$D$가 B$B$에서 가장 먼저 등장한 위치를 출력하면 된다. 단, D$D$가 B$B$에 존재하지 않는 경우에는 -1를 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.

제한

• 1 ≤ N ≤ 2×10^5
• 1 ≤ M ≤ 2×10^5
• -109 ≤ A_i ≤ 10^9
• -109 ≤ D ≤ 10^9

---

 

이 문제는 문제 지문에 나온 그대로 하면 되는 문제인데, 여기서 딱 하나 생각해야하는 부분이

질문으로 주어진 정수가 존재하는지 아닌지, 만약 존재한다면 정렬된 배열에서 어느 위치에 존재하는지이다.

그리고 이것을 단순히 구현하는 것이 아닌 문제의 제한 요구를 파악한 후 O(n)보다 효율성을 높여 이분 탐색으로 문제를 해결해야 이 문제의 요구에 맞게 해결할 수 있다.

 

나는 C++의 Algorithm헤더 파일이 제공하는 binary_search를 이용하여 찾고자 하는 값이 존재하는지 존재하지 않는지 확인부터 한 후, 존재하지 않으면 바로 -1을 출력하고 존재한다고 하면 찾고자 하는 값을 찾아주었다.

 

값을 찾을 때에도 lower_bound를 이용하면 찾고자 하는 값 이상이 처음으로 나오는 위치를 알 수 있고, 우리는 같은 값을 찾기 때문에 정렬된 배열에서 바로 찾고자 하는 값의 위치를 알 수 있다.

 

위 내용을 코드로 확인할 수 있다.

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl

using namespace std;

int N, M;
vector<int> initArray;

void input() {
	cin >> N >> M;
	initArray = vector<int>(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> initArray[i];
	}
}

void solution() {
	sort(initArray.begin(), initArray.end());
	for (int i = 0; i < M; i++) {
		int findNum; 
		cin >> findNum;

		if (!binary_search(initArray.begin(), initArray.end(), findNum)) {
			cout << -1 << endl;
		}
		else {
			cout << lower_bound(initArray.begin(), initArray.end(), findNum) - initArray.begin() << endl;
		}
	}
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}