백준 20551번: Sort 마스터 배지훈의 후계자 (C++)

 

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

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

 

풀이

처음 입력받은 배열 A의 위치를 반환하지 않아도 돼서 편하게 풀 수 있는 이분 탐색 문제.

map으로 구현해도 될 것 같지만 중복된 숫자가 있어서 이분 탐색이 편한 듯 하다.

 

left 를 배열의 첫번째 인덱스인 0, right 를 마지막 인덱스로 설정하고 탐색을 진행했다.

구해야 하는 것이 처음으로 등장한 위치기 때문에 is_possible 함수를 D 가 더 작을 때 true를 반환하게 해주었다.

그리고 v[mid] 와 D 가 같을 때만 ret 을 갱신시켜서

같은 게 존재하지 않을 경우 ret 이 갱신되지 않아 -1을 출력하도록 했다.

 

전체 코드

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

using namespace std;

int N, M, D;
vector<int> v;

bool is_possible(int mid) {
	if (v[mid] >= D) return true;
	return false;
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}

	sort(v.begin(), v.end());

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

		int left = 0, right = v.size() - 1, ret = -1;

		while (left <= right) {
			int mid = (left + right) / 2;

			if (is_possible(mid)) {
				if (v[mid] == D) ret = mid;
				right = mid - 1;
			}
			else left = mid + 1;
		}
		cout << ret << '\n';
	}
}