c++ 7469번 K번째 수 (백준)

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

using namespace std;

int arr[100001];
vector<int> tree[400001];

void update(int s, int e, int node, int index, int val) { //merge sort tree 수정
	if(s > index || e < index) return;
	tree[node].push_back(val);
	if(s == e) return;
	int m = (s+e)/2;
	update(s, m, node*2, index, val);
	update(m+1, e, node*2+1, index, val);
}

int find(int s, int e, int node, int l, int r, int key) { //merge sort tree에서 node 에 있는 내용 중 key값 이하인 개수를 리턴 
	if(s > r || e < l) return 0;
	if(l <= s && e <= r) {
		//upper_bound을 이용하여 key 이하인 요소들의 개수를 리턴
		int left=0, right=tree[node].size(), mid;
		while(left < right) {
			mid = (left+right)/2;
			if(tree[node][mid] <= key) left = mid+1;
			else right = mid;
		} return right;
	}
	int m = (s+e)/2;
	return find(s, m, node*2, l, r, key) + find(m+1, e, node*2+1, l, r, key);

}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) {
		scanf("%d", &arr[i]);
		update(1, n, 1, i, arr[i]);
	}
	
	for(int i=1; i<=400000; i++) //만들어진 merge sort tree들의 노드들을 오름차순 정렬함
		sort(tree[i].begin(), tree[i].end());
	
	
	while(m--) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		
		int left = -1e9, right = 1e9, mid; //왼쪽을 -1*10^9 오른쪽을 10^9로 잡은다음
        //이분탐색을 통해 특정 범위에서, 원하는 수를 탐색합니다.
        //쿼리에서 입력된 c보다 적다면 왼쪽을 증가시키고
        //쿼리에서 입력된 c보다 크거나 같다면 오른쪽을 증가시킵니다.
        //탐색이 종료되려면 left의 값은 find시 c 이상을 return 하며
        //right의 값은 find시 c-1 이하를 return 합니다.
        //탐색 종료후 사용하는 값은 left 입니다.
		
		while(left <= right) {
			mid = (left+right)/2;
			if(find(1, n, 1, a, b, mid) < c) left = mid+1;
			else right = mid-1;
		} printf("%d\n", left);
	
	}
}

 

풀이 : merge sort tree, 이분탐색, upper_bound

 

1. merge sort tree을 위한 공간을 자동할당하고, 이를 위한 함수들도 생성합니다.

2. 요소들을 입력받고 그걸로 merge sort tree을 생성합니다.

3. merge sort tree의 모든 노드들의 요소들을 오름차순 정렬합니다

 

4. 쿼리를 입력받습니다.

 

여기서 중요한 것은 특정 범위에서, 범위내의 요소들을 오름차순 정렬했을 때, 몇번째 요소를 리턴해야 하는 것 입니다.

 

범위가 여러 노드들을 다룰 수 있기 때문에 바로 몇번째 요소를 구할 수는 없으나

upper_bound을 이용하여 범위내에서, 특정 값 이하인 요소들의 개수들은 알 수 있습니다.

 

즉 이분탐색을 통해 자신과 같거나 미만인 요소들의 개수가 쿼리에서 주어진 값과 비교해서 답을 얻어낼 수 있습니다.

 

ex)

1 5 2 6 3 7 4

1 7 3 : 1부터 7번째까지의 요소들 중 오름차순 정렬시 3번째로 위치한 값을 구해라

 

위의 값들은 오름차순 정렬시 1 2 3 4 5 6 7 입니다.

 

여기서 3번째로 위치한 값을 구하는 것은 이분탐색을 이용해서 구할 수 있습니다.

 

첫번째 : left = -10^9 right = 10^9 mid = 0

merge sort tree의 find을 이용해서 key값을 mid = 0 으로 주면, 0 이하인 요소는 0개 이므로 0이 리턴되며,

0 < 3 이므로

left = mid + 1 = 1 이 됩니다.

 

두번째 : left = 1 right = 10^9 mid = 5*10^8

merge sort tree의 find을 이용해서 key값을 mid = 5*10^8 으로 주면, 5*10^8이하인 요소는 7개 이므로 7이 리턴되며,

7 >= 3 이므로

right = mid-1 = 499999999 가 됩니다.

 

세번째 : left = 1, right = 499999999, mid = 250,000,000

리턴값이 7 >= 3 이므로

right = mid-1 = 249999999 가 됩니다.

 

네번째 : left = 1, right = 249999999, mid = 125,000,000

리턴값이 7>=3 이므로

right = mid-1 = 124999999 가 됩니다.

 

다섯번째 : left = 1, right = 124999999 , mid = 62,500,000

리턴값이 7>=3 이므로

right = mid-1 = 62499999 가 됩니다.

 

여섯번째 : left = 1, right = 62499999 , mid = 31,250,000

리턴값이 7>=3 이므로

right = mid-1 = 31249999 가 됩니다.

 

일곱번째 : left = 1, right = 31249999 , mid = 15,625,000

리턴값이 7>=3 이므로

right = mid-1 = 15624999 가 됩니다.

 

여덟번째 : left = 1, right = 15624999 , mid = 7,812,500

리턴값이 7>=3 이므로

right = mid-1 = 7812499 가 됩니다.

 

아홉번째 : left = 1, right = 7812499 , mid = 3,906,250

리턴값이 7>=3 이므로

right = mid-1 = 3906249 가 됩니다.

 

열번째 : left = 1, right = 3906249 , mid = 1,953,125

리턴값이 7>=3 이므로

right = mid-1 = 1953124 가 됩니다.

 

열한번째 : left = 1, right = 1953124 , mid = 976,562

리턴값이 7>=3 이므로

right = mid-1 = 976,561 가 됩니다.

 

열한번째 : left = 1, right = 976,561, mid = 488,281

리턴값이 7>=3 이므로

right = mid-1 = 488,280 가 됩니다.

 

열두번째 : left = 1, right = 488,280 , mid = 244,140

리턴값이 7>=3 이므로

right = mid-1 = 244,139 가 됩니다.

 

열세번째 : left = 1, right = 244,139  , mid = 122,070

리턴값이 7>=3 이므로

right = mid-1 = 122,069 가 됩니다.

 

열네번째 : left = 1, right = 122,069  , mid = 61,035

리턴값이 7>=3 이므로

right = mid-1 = 61,034 가 됩니다.

 

열다섯번째 : left = 1, right = 61,034  , mid = 30,517

리턴값이 7>=3 이므로

right = mid-1 =30,516 가 됩니다.

 

열여섯번째 : left = 1, right = 30,516  , mid = 15,258

리턴값이 7>=3 이므로

right = mid-1 =15,257 가 됩니다.

 

열일곱번째 : left = 1, right =15,257   , mid = 7,629

리턴값이 7>=3 이므로

right = mid-1 =7,628 가 됩니다.

 

열여덟번째 : left = 1, right =7,628   , mid = 3,814

리턴값이 7>=3 이므로

right = mid-1 =3,813 가 됩니다.

 

열아홉번째 : left = 1, right =3,813  , mid = 1,907

리턴값이 7>=3 이므로

right = mid-1 =1,906 가 됩니다.

 

스무번째 : left = 1, right =1,906 , mid = 953

리턴값이 7>=3 이므로

right = mid-1 =952 가 됩니다.

 

스물한번째 : left = 1, right =952 , mid = 476

리턴값이 7>=3 이므로

right = mid-1 =475 가 됩니다.

 

스물두번째 : left = 1, right =475 , mid = 238

리턴값이 7>=3 이므로

right = mid-1 =237 가 됩니다.

 

스물세번째 : left = 1, right =237, mid = 238

리턴값이 7>=3 이므로

right = mid-1 =118 가 됩니다.

 

스물네번째 : left = 1, right =118, mid = 59

리턴값이 7>=3 이므로

right = mid-1 =58 가 됩니다.

 

스물다섯번째 : left = 1, right =58 ,  mid = 29

리턴값이 7>=3 이므로

right = mid-1 =28 가 됩니다.

 

스물여섯번째 : left = 1, right =28 ,  mid = 14

리턴값이 7>=3 이므로

right = mid-1 =13 가 됩니다.

 

스물일곱번째 : left = 1, right =13 ,  mid =7

리턴값이 7>=3 이므로

right = mid-1 =6가 됩니다.

 

스물여덟번째 : left = 1, right =6 ,  mid =3

리턴값이 3>=3 이므로

right = mid-1 =2가 됩니다.

 

스물아홉번째 : left = 1, right =2 ,  mid =1

리턴값이 1<3 이므로

left = mid+1 =2가 됩니다.

 

서른번째 : left = 2, right =2 ,  mid =2

리턴값이 2<3 이므로

left = mid+1 =3가 됩니다.

 

여기서 left > right가 됬기에 이분탐색을 종료합니다.

 

4.1 여기서 사용하는 upper_bound 는 이분탐색과 비슷하나 조금 다릅니다.

 

upper_bound는 이분탐색처럼 무언가를 찾는 것은 맞으나, 그 중에서도 오름차순 정렬된 데이터에서 특정한 key보다 더 큰 값이 존재하기 시작하는 index을 반환하는 것이 목적입니다 (여기서 index가 특정한  key값 이하인 요소들의 개수와 같은 의미도 가집니다)

 

범위 : left = 0, right =  탐색하는 데이터의 개수

반복문 조건 : left < right  (이분탐색은 left <= right)

조건문 : 특정한 key보다 같거나 작다면 left = mid + 1, else right = mid (이분탐색은 특정한 값보다 작으면 left = mid+1, else right = mid -1;)

사용하는 값 : right (key값보다 큰 요소가 맨 처음 나오기 시작하는 index = key값이하인 요소들의 개수) (이분탐색은 left을 사용합니다)

 

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

7469번: K번째 수