[BOJ 27198 // C++] kex

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27198번 문제인 kex이다.
문제는 아래 링크를 확인하자.

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

27198번: kex

주어진 N개의 정수에 포함되지 않은 수 중 k번째로 작은 수를 찾는 쿼리를 여러 개 처리해야 하는 문제이다.

 

음이 아닌 정수 x에 대하여 f(x)를 x 이하의 수 중 주어진 수에 없는 수의 개수로 정의하자. 이 때, f(x)의 값은 x가 증가함에 따라 단조증가함을 관찰할 수 있다. 따라서 f(x)를 계산할 수 있다면 문제의 답은 f(x)를 이용한 이진탐색으로 빠르게 구해낼 수 있음을 알 수 있다.

 

f(x)의 값은 x 이하의 수의 개수(x+1)에서 주어진 수에 포함되어있는 x 이하의 수의 개수를 빼는 것으로 계산할 수 있다. 주어진 수에 포함되어있는 x 이하의 수의 개수는 또다른 이진탐색을 통해 구해낼 수 있음을 이용해 문제를 해결해내자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int N, Q;
int arr[100001];

int func(int x) {
	int L = 0, R = N;
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		if (arr[mid] <= x) L = mid;
		else R = mid - 1;
	}

	return L;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;
	
	arr[0] = -1;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N + 1);

	while (Q--) {
		int K; cin >> K;
		int L = 0, R = 1011111111;
		while (L < R) {
			int mid = (L + R) / 2;
			int val = (mid + 1) - func(mid);
			if (val < K) L = mid + 1;
			else R = mid;
		}
		cout << L << ' ';
	}
}