백준 7469 c++ "K번째 수" -PlusUltraCode-

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

[필자 사고]

이 문제는 2차원 세그먼트 트리 구조를 이용해야 풀 수 있는 문제이다.

이 문제만의 매력은 lower_bound를 사용하여 몇번째인지 찾은 뒤

이진 탐색을 통해 K번째 수를 찾는 과정이다.

필자는 이진 탐색을 이용해 K번째 수를 찾는 방법을 생각하지 못하여 틀린 문제이다.

 

많은걸 배울 수 있어서 좋은 문제 같다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input 함수는 문제의 입력 데이터를 처리합니다.

1. N과 M을 입력받습니다.
   • N: 배열의 크기
   • M: 질의(query)의 개수
2. 배열 arr를 초기화하고 크기 N만큼 값을 입력받습니다.

이 함수는 입력 데이터를 효율적으로 관리하고, 세그먼트 트리를 생성하기 위한 기초 데이터를 제공합니다.

---

3. 세그먼트 트리 초기화 (Init_Tree 함수)

Init_Tree 함수는 세그먼트 트리를 구축합니다.

1. 기저 사례:
   • start == end일 때, 트리 노드에는 arr[start] 값을 저장합니다.
2. 재귀적 분할:
   • 구간을 절반씩 나누어 왼쪽 자식과 오른쪽 자식을 초기화합니다.
   • tree[node]는 왼쪽 자식과 오른쪽 자식의 정렬된 값을 병합(merge)한 결과입니다.
3. merge 함수:
   • STL의 merge를 사용하여 정렬된 두 벡터를 하나로 합칩니다.
   • 결과는 tree[node]에 저장됩니다.

이 과정은 시간 복잡도가 O(Nlog⁡N)O(N \log N)O(NlogN)으로 효율적입니다.

---

4. 구간 내 값의 개수 찾기 (Query 함수)

Query 함수는 특정 구간 [left, right]에서 주어진 값보다 작은 값의 개수를 구합니다.

1. 구간 겹침 확인:
   • 완전히 겹치지 않는 경우 0을 반환합니다.
   • 완전히 포함된 경우, lower_bound를 사용하여 tree[node]에서 주어진 값보다 작은 원소의 개수를 구합니다.
2. 부분 겹침 처리:
   • 왼쪽 자식과 오른쪽 자식을 재귀적으로 호출하여 결과를 합산합니다.

이 함수는 구간 내 값 개수를 계산하는 핵심 함수로, K번째 작은 값을 찾기 위한 기반이 됩니다.

---

5. K번째 작은 값 찾기 (Kth_Smallest 함수)

Kth_Smallest 함수는 특정 구간 [left, right]에서 K번째 작은 값을 찾습니다.

1. 이분 탐색:
   • 값의 범위 (low, high)를 기준으로 이분 탐색을 수행합니다.
   • 중간값 mid에 대해 Query를 호출하여 mid보다 작은 값의 개수를 구합니다.
2. K와의 비교:
   • 작은 값의 개수가 k보다 작으면 low를 증가시킵니다.
   • 그렇지 않으면 high를 감소시킵니다.
3. 결과 반환:
   • 이분 탐색이 끝난 후, 구간 내 K번째 작은 값을 반환합니다.

이 함수는 이분 탐색과 **구간 내 값 개수 계산(Query 함수)**를 결합하여 효율적으로 동작합니다.

---

6. 메인 함수 (main 함수)

main 함수는 프로그램의 주요 흐름을 담당합니다.

1. 입력 데이터를 처리합니다.
2. 세그먼트 트리를 초기화합니다.
3. M개의 질의를 처리하여 각 결과를 출력합니다.
   • 각 질의는 [a, b] 구간에서 c번째 작은 값을 찾는 작업입니다.

---

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

vector<vector<ll>> tree;
vector<ll> arr;
int N, M;

void Init_Tree(int node, int start, int end) {
    if (start == end) {
       
        tree[node].push_back(arr[start]);
        return;
    }
    tree[node].resize(end - start + 1);

    int mid = (start + end) / 2;
    Init_Tree(node * 2, start, mid);
    Init_Tree(node * 2 + 1, mid + 1, end);

  
    merge(all(tree[node * 2]), all(tree[node * 2 + 1]), tree[node].begin());
}

ll Query(int node, int start, int end, int left, int right, ll val) {
    if (left <= start && end <= right) {
      
        return lower_bound(all(tree[node]), val) - tree[node].begin();
    }
    if (end < left || right < start) return 0;

    int mid = (start + end) / 2;
    return Query(node * 2, start, mid, left, right, val) +
        Query(node * 2 + 1, mid + 1, end, left, right, val);
}

ll Binary_Search(int left, int right, ll K) {
    ll start = -1e9, end = 1e9; 

    while (start <= end) {
        int mid = (start + end) / 2;
        ll count = Query(1, 0, N - 1, left, right, mid);

        if (count < K) {
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    return start; 
}

void Input() {
    cin >> N >> M;
    tree.resize(N * 4); 
    arr.resize(N); 

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
}


void Game_Start() {
    Init_Tree(1, 0, N - 1); 

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        cout << Binary_Search(a, b, c) << '\n'; 
    }
}

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

    Input();      
    Game_Start();

    return 0;
}