[Java] 백준 #24060 (재귀)

📍 출처

출처 : https://www.acmicpc.net/problem/24060

📝 문제

오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

⌨️ 입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 10^8)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 10^9)

🖨 출력

배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

⌨️ 예제 입력 1

5 7
4 5 1 3 2

🖨 예제 출력 1

3

⌨️ 예제 입력 2

5 13
4 5 1 3 2

🖨 예제 출력 2

-1

📚 내가 제출한 코드

import java.util.Scanner;

public class Main {
    
        static int[] temp;
        static int count = 0;
        static int K;
        static int result = -1;
    
        public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        int[] arr = new int[num];
        K = sc.nextInt();

        temp = new int[num];

        for(int i = 0 ; i < num ; i++){
            arr[i] = sc.nextInt();
        }

        sc.close();

        merge_sort(arr, 0, arr.length - 1);
        System.out.print(result);

      }

        static void merge_sort(int A[], int low, int high){

            if(low < high){
                int mid = (low + high) / 2;
                merge_sort(A, low, mid);
                merge_sort(A, mid + 1, high);
                merge(A, low, mid, high);
            }
        }

static void merge(int A[], int low, int mid, int high){
        int i = low;
        int j = mid + 1;
        int t = 0;

        
        while(i <= mid && j <= high){
            if(A[i] <= A[j]){
                temp[t++] = A[i++];
            }else{
                temp[t++] = A[j++];
            }
        }

        while(i <= mid){
            temp[t++] = A[i++];
        }

        while(j <= high){
            temp[t++] = A[j++];
        }

        t = 0;
        i = low;

        while(i <= high){
            count++;
            if(count==K){
                result = temp[t];
                break;
            }
            A[i++] = temp[t++];
        }     
   }
}

✏️ 내가 제출한 코드에 대한 설명

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

합병 정렬은 다음의 단계들로 이루어진다.

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

사진으로 보면 이러하다.

하지만 우리는 정렬을하여 출력하는 것이 아닌 K번째 저장되는 수를 출력하는 것이 목적이니 K를 입력받고 count로 값이 저장될 때마다 1씩 값을 더하여준다. 그리고 만약 count가 더해지다 K와 같아진다면 그때 저장되는 값을 출력해주고 값이 저장될때까지 K == count를 만나지 못한다면 -1을 출력해주면 된다.