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

1 개요

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

• 백준 온라인 저지 24060번 문제
• BOJ 21단계

2 C++

#include <iostream>
using namespace std;

void merge_sort(int* A, int p, int r);
void merge(int* A, int p, int q, int r);

int N, K;
int A[500000];
int tmp[500000];
int saveCount = 0;
int savedNumber = -1;

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

void merge(int* A, int p, int q, int r) {
    int i = p, j = q+1, t = 1;
    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 = 1;
    while(i <= r){
        A[i++] = tmp[t++];
        saveCount++;
        if(saveCount == K) savedNumber = tmp[t-1];
    }
}

int main() {
    cin >> N >> K;
    for(int i=0; i<N; i++) {
        cin >> A[i];
    }
    merge_sort(A, 0, N-1);
    cout << savedNumber;
}