[백준 11004] K번째 수 (Java)

🚀 문제 분석

• 입력: 데이터 개수 $N(1 \leq N \leq 5,000,000)$, 찾고자 하는 순서 $K$
• 특징: 데이터가 500만 개로 매우 많기 때문에, 전체를 정렬하는 $O(N \log N)$ 방식보다 더 효율적인 접근이 필요합니다.
• 핵심: 정렬 알고리즘의 파티션(Partition) 원리를 활용해 특정 위치의 값만 찾아내는 Quick Selection 알고리즘을 적용합니다.

💡 Quick Selection 알고리즘 원리

Quick Selection은 퀵 정렬과 유사하지만, 분할 후 $K$가 포함된 구역만 재귀적으로 탐색하여 평균 시간 복잡도 $O(N)$을 보장합니다.

1. Pivot 선택: 배열에서 기준이 될 피벗을 선택합니다.
2. Partition: 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 보냅니다.
3. Branching:
   • 피벗의 최종 위치가 $K-1$과 같다면 탐색을 종료합니다.
   • 피벗 위치가 $K-1$보다 크면 왼쪽 구역만 다시 탐색합니다.
   • 피벗 위치가 $K-1$보다 작면 오른쪽 구역만 다시 탐색합니다.

🛠️ 구현 디테일: 피벗 최적화

데이터가 많을 때 피벗을 단순히 맨 앞이나 뒤로 잡으면 최악의 경우 $O(N^2)$에 빠질 수 있습니다. 이를 방지하기 위해 배열의 중간값을 피벗으로 설정하는 로직을 추가했습니다.

int m = (s + e) >>> 1; // 중간 인덱스 계산
swap(arr, s, m);       // 중간값을 맨 앞으로 보내 피벗으로 사용

💻 구현 코드 (Java)

import java.io.*;
import java.util.*;

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

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

        quickSelect(a, 0, n - 1, k);
        System.out.println(a[k - 1]);
    }

    private static void quickSelect(int[] arr, int s, int e, int k) {
        if (s >= e) return;

        int pivot = partition(arr, s, e);

        if (pivot == k - 1) return;
        else if (pivot > k - 1) quickSelect(arr, s, pivot - 1, k);
        else quickSelect(arr, pivot + 1, e, k);
    }

    private static int partition(int[] arr, int s, int e) {
        // 중간값 피벗 설정으로 최악의 케이스 방지
        int m = (s + e) >>> 1;
        swap(arr, s, m);

        int pivot = arr[s];
        int i = s + 1, j = e;

        while (i <= j) {
            while (i <= j && arr[j] > pivot) j--;
            while (i <= j && arr[i] < pivot) i++;
            if (i <= j) swap(arr, i++, j--);
        }

        swap(arr, s, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

🧐 학습 포인트

• 불필요한 연산 제거: 전체 정렬이 필요 없는 'K번째 수 찾기' 문제에서 Quick Selection이 왜 효율적인지 동작 구조를 통해 이해할 수 있었습니다.
• Partition의 활용: 퀵 정렬의 핵심인 Partition 로직이 정렬 외에도 탐색 등 다양한 최적화에 활용될 수 있음을 확인했습니다.
• Pivot과 성능: 대량 데이터 처리 시 피벗 선택 방식이 전체 수행 시간에 미치는 결정적인 영향을 체감했습니다.