📘 문제

문제링크 : https://www.acmicpc.net/problem/24060 (단계별로 풀어보기 : 재귀)

📝 문제 풀이

일단 문제를 풀기 전에 합병 정렬(=병합정렬)을 알아야 문제의 의사 코드를 이해하는 데 도움이 된다. 이 링크를 통해서 그림을 보며 이해하면 좋을 것 같다. 말로 간단히 설명하자면 초기 상태에서 가운데를 기준으로 왼쪽 오른쪽을 나누고 그 나누어진 두 곳에서 각각의 가운데를 찾아 나누는 과정을 반복하여 최소단위로 나눈 후 다시 나눈 두 부분을 합치면서 정렬하는 과정을 반복하여 전체를 정렬하는 방식이다. 해당 문제에서는 의사 코드가 나와 있기 때문에 문제를 푸는 데에는 약간의 코드만 수정해주면 좋을 것 같다. 문제에서 중요한 부분은 K 번째로 A 배열에 입력되는 수를 찾는 것이기 때문에 A 배열에 저장되는 순번을 전역변수로 사용하여 해당 변수가 K가 될 시 배열에 넣었던 수를 출력하는 코드를 추가해주었다. (알고리즘 문제 풀이에서는 전역변수를 많이 쓰기는 하지만, 전역변수를 최대한 안 쓰도록 코드를 작성하는 것이 좋다.)

✏️ 알고리즘 스케치

( 해당 문제는 알고리즘 스케치라고 할 것도 없다...)

💻 소스코드

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

void merge_sort(int* A, int start, int end, int K);
void merge(int* A, int p, int q, int r, int K);
int inputcnt = 0;

int main(){
    fastio;
    int N, K;
    cin >> N >> K;
    int* A;
    A = new int[N];
    for(int i=0; i<N; i++)
        cin >> A[i];
    merge_sort(A,0,N-1,K);
    if(inputcnt<K) cout << -1;
    // for(int i=0; i<N; i++)		//정렬 확인용 출력 
    //     cout << A[i] << " ";
    return 0;
}

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

void merge(int* A, int p, int q, int r, int K){
    int tmp[r+2];   //tmp배열은 인덱스 1부터 사용
    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++];
        if(++inputcnt==K)   cout << tmp[t-1];
    }
}