[백준 JAVA] 24060. 알고리즘 수업 - 병합 정렬 1

문제 링크

---

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

접근 방법

---

병합 정렬을 구현하면서 배열에 값을 저장하는 횟수를 카운팅합니다.
k번째 저장이 발생할 때 그 값을 출력하고 종료합니다.
merge 단계에서 값을 실제 배열로 복사할 때마다 카운트를 증가시키고, k에 도달하면 해당 값을 결과로 저장합니다.

소스 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {

    static int[] arr, tmp;
    static int cnt = 0, k, rst;

    public static void merge(int p, int q, int r) {
        int i = p, j = q + 1, t = 0;

        while (i <= q && j <= r) {
            if (arr[i] <= arr[j]) {
                tmp[t++] = arr[i++];
            } else {
                tmp[t++] = arr[j++];
            }
        }

        while (i <= q) {
            tmp[t++] = arr[i++];
        }

        while (j <= r) {
            tmp[t++] = arr[j++];
        }

        i = p;
        t = 0;
        while (i <= r) {
            if (++cnt == k) {
                rst = tmp[t];
                return ;
            }
            arr[i++] = tmp[t++];
        }
    }

    public static void mergeSort(int p, int r) {
        if (p < r && cnt < k) {
            int q = (p + r) / 2;
            mergeSort(p, q);
            mergeSort(q + 1, r);
            merge(p, q, r);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        rst = -1;

        arr = new int[n];
        tmp = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        mergeSort(0, n - 1);
        System.out.println(rst);
    }
}

코드 설명

---

병합 정렬에서 실제 배열에 복사하는 시점을 기준으로 몇 번째 저장인지 cnt로 체크합니다.
cnt == k일 때의 값을 rst에 저장하고, 정렬을 종료합니다.
값이 k회 미만이면 -1이 출력됩니다.