24060번: 알고리즘 수업 - 병합 정렬 1

24060번: 알고리즘 수업 - 병합 정렬 1

사용 언어: C++

 

풀이

Merge Sort (병합 정렬) 문제.

기본 병합 정렬 구현 문제. 핵심은 정렬이 완료된 배열이 아니라, 정렬 중 원소가 배열 A에 저장되는 순간을 추적해서,
K번째로 저장되는 값을 출력하는 것.

병합 과정에서 A[i] = tmp[t]가 실행될 때마다 저장 횟수(cnt)를 세고,
cnt == K가 되면 해당 값을 result에 저장한다.

만약 저장 횟수가 K보다 작으면 -1 출력.

#include <iostream>
using namespace std;

int A[500001], tmp[500001];
int N, K, cnt = 0, result = -1;

void merge(int p, int q, int r) {
    int i = p, j = q + 1, t = 0;
    while (i <= q && j <= r) {
        if (A[i] <= A[j]) tmp[t++] = A[i++];
        else tmp[t++] = A[j++];
    }
    while (i <= q) tmp[t++] = A[i++];
    while (j <= r) tmp[t++] = A[j++];

    i = p; t = 0;
    while (i <= r) {
        A[i++] = tmp[t++];
        cnt++;
        if (cnt == K) {
            result = A[i - 1];
            break;
        }
    }
}

void merge_sort(int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(p, q);
        merge_sort(q + 1, r);
        merge(p, q, r);
    }
}

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

    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> A[i];

    merge_sort(0, N - 1);
    cout << result << '\n';
    return 0;
}