[알고리즘] 백준 7469번: K번째 수 (C++)

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

7469번: K번째 수

부분 배열의 정렬이 필요해서 머지 소트 트리가 필요한 문제라고 느꼈다.

문제는 그다음인데 k번째 수를 가져오기 위해 쿼리 함수를 작성하는 게 어려웠다.

>> 쿼리 함수는 어떤 값보다 작은 원소의 개수를 카운트할 수 있도록 작성해주었다.

+ 이분 탐색 사용

 

여기다가 어떤 값들이 들어갈지 모르고, 그 값의 범위가 크기 때문에 이분 탐색을 고려할 수 있었다.

모든 값들을 넣기엔 시간이 부담스럽기 때문이다.

 

이번 문제의 핵심은

• 머지 소트 트리 떠올리기
• 이분 탐색을 통해 여러 값들을 쿼리에 넣어 어떤 값이 k번째 수인지 알 수 있도록 구현하는 아이디어

[AC 코드]

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

vector<int> msTree[400000 + 1];
vector<int> arr;
int n, m;

void init(int node, int start, int end){
    if(start == end) msTree[node].push_back(arr[start]);
    else{
        msTree[node].resize(end - start + 1);
        int mid = (start + end) >> 1;
        init(2 * node, start, mid);
        init(2 * node + 1, mid + 1, end);
        merge(msTree[2 * node].begin(), msTree[2 * node].end()
        ,msTree[2 * node + 1].begin(), msTree[2 * node + 1]. end()
        ,msTree[node].begin());
    }
}

int query(int node, int start, int end, int left, int right, int val){
    if(start > right || end < left){
        return 0;
    }
    if(left <= start && end <= right){
        return upper_bound(msTree[node].begin(), msTree[node].end(), val)
        - msTree[node].begin();
    }
    
    int mid = (start + end) >> 1;
    return query(node * 2, start, mid, left, right, val)
    + query(node * 2 + 1, mid + 1, end, left, right, val);
}

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;
        arr.push_back(a);
    }
    
    init(1, 0, n - 1);
    
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        
        // 각 정수는 절댓값이 10^9를 넘지 않는 정수이다.
        int low = -1e9;
        int high = 1e9;
        int ans = 0;
        
        // 이분 탐색을 통해 어떤 값이 k번째 수인지 확인 한다.
        while(low <= high){
            int mid = (low + high) >> 1;
            int temp = query(1, 0, n - 1, a - 1, b - 1, mid);
            
            if(temp < c){
                low = mid + 1;
            }
            else{
                ans = mid;
                high = mid - 1;
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}