백준 24060 Java 풀이: 병합 정렬의 K번째 저장 값 찾기

백준 24060번 ‘알고리즘 수업 - 병합 정렬 1’은 정렬된 결과만 구하는 문제가 아니다. 문제에 제시된 병합 정렬 의사 코드가 임시 배열의 값을 원본 배열 A에 다시 저장할 때마다 횟수를 세고, K번째로 저장되는 값을 출력해야 한다.

• 백준 24060번 문제

저장 횟수를 세는 위치

병합 과정은 두 단계로 나뉜다.

1. 두 정렬 구간을 비교해 tmp에 넣는다.
2. tmp의 값을 원본 배열 A[p..r]에 복사한다.

문제에서 말하는 저장은 두 번째 단계다. tmp에 넣을 때 횟수를 올리면 문제의 의사 코드와 다른 순서를 세게 된다.

tmp에 병합 결과 만들기
  → A[p]부터 tmp 값을 다시 저장
  → A에 한 값을 쓸 때마다 count 증가
  → count == K이면 방금 쓴 값 기록

Java 코드

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

public class Main {
    static int[] numbers;
    static int[] temp;
    static long saveCount;
    static long targetCount;
    static int answer = -1;

    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());
        targetCount = Long.parseLong(st.nextToken());

        numbers = new int[n];
        temp = new int[n];

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

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

    static void mergeSort(int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = (left + right) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }

    static void merge(int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int t = 0;

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

        while (i <= mid) {
            temp[t++] = numbers[i++];
        }
        while (j <= right) {
            temp[t++] = numbers[j++];
        }

        for (int k = left, index = 0; k <= right; k++, index++) {
            numbers[k] = temp[index];
            saveCount++;

            if (saveCount == targetCount) {
                answer = numbers[k];
            }
        }
    }
}

예제 흐름

5 7
4 5 1 3 2

원본 배열에 저장되는 값의 앞부분은 다음 순서다.

1, 4, 5, 1, 3, 2, 3, ...

일곱 번째 값은 3이므로 출력은 다음과 같다.

3

전체 저장 횟수가 K보다 작으면 answer가 초기값 -1에서 바뀌지 않는다.

기존 코드에서 다시 확인한 부분

원래 풀이도 A에 복사하는 루프에서 횟수를 세는 핵심은 맞았다. 다만 System.exit(0)으로 중간 종료하면 흐름을 따라가기 어렵고, count > K 조건은 K번째를 찾은 순간 이미 프로세스가 끝나 실질적인 의미가 없었다.

수정한 코드는 정렬을 끝까지 수행하되 K번째 값만 한 번 기록한다. 입력의 K 범위를 넉넉히 담도록 횟수는 long으로 두었다.

복잡도

• 시간 복잡도: O(N log N)
• 추가 공간: O(N)

이 문제의 포인트는 병합 정렬 자체보다 의사 코드의 관찰 지점을 정확히 코드로 옮기는 데 있다.