[백준] 24060번(Java)

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

[ 문제 ]
오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
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++]; 
}

💡풀이

• 병합 정렬의 개념에 대해 처음 접해봐서 조금 어렵게 느껴진 문제였다.
• 주어진 배열을 2개씩 나눠서 오름차순으로 정렬한 뒤, 하나로 병합하는 것을 병합 정렬이라고 한다.
• 두 개의 정렬된 배열들을 하나로 합칠 때, 각 배열의 앞에 있는 값들을 비교해서 더 작은 값을 결과 배열에 저장한다. 더 작은 값을 가지던 배열의 제일 앞에 있는 값은 그 뒤의 값으로 바뀐다.
• 이 후 둘 중 숫자가 남은 배열이 있다면 그 배열을 그대로 결과 배열 뒤에 붙여주는 방식으로 구현했다.
• ex) [1, 3, 8, 10, 11] , [2, 4, 5, 7, 15]
  • result : [1] / [3, 8, 10, 11] , [2, 4, 5, 7, 15]
  • result : [1, 2] / [3, 8, 10, 11] , [4, 5, 7, 15]
  • result : [1, 2, 3] / [8, 10, 11] , [4, 5, 7, 15]
  • result : [1, 2, 3, 4] / [8, 10, 11] , [5, 7, 15]
  • result : [1, 2, 3, 4, 5] / [8, 10, 11] , [7, 15]
  • result : [1, 2, 3, 4, 5, 7] / [8, 10, 11] , [15]
  • result : [1, 2, 3, 4, 5, 7, 8] / [10, 11] , [15]
  • result : [1, 2, 3, 4, 5, 7, 8, 10] / [11] , [15]
  • result : [1, 2, 3, 4, 5, 7, 8, 10, 11] / [15]
  • result : [1, 2, 3, 4, 5, 7, 8, 10, 11, 15]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] ans;
    static int[] tmp;
    static int res;
    static int cnt;

    static int N;  //배열 A의 크기
    static int K;  //저장 횟수

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        ans = new int[N];
        tmp = new int[N];
        cnt = 0;
        res = -1;
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for(int i = 0; i < N ; i ++){
            ans[i] = Integer.parseInt(st1.nextToken());
        }

        merge_sort(0, N-1);
        System.out.println(res);

    }
    public static void merge_sort(int start, int end){
        if(start < end){
            int mid = (start + end) / 2;
            merge_sort(start, mid);
            merge_sort(mid + 1, end);
            merge(start, mid, end);
        }
    }
    public static void merge(int start, int mid, int end){
        int mid1 = mid + 1;
        int idx = start;
        int tmps = start;
        int tmpe = end;

        while(start <= mid && mid1 <= end){
            if(ans[start] < ans[mid1]){
                tmp[idx++] = ans[start++];
            } else {
                tmp[idx++] = ans[mid1++];
            }
        }

        while(mid1 <= end){
            tmp[idx++] = ans[mid1++];
        }
        while(start <= mid){
            tmp[idx++] = ans[start++];
        }
        for(int i = tmps ; i < tmpe + 1; i ++){
            ans[i] = tmp[i];
            cnt += 1;
            if(cnt == K){
                res = tmp[i];
                return;
            }
        }
    }
}

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