문제 개요

정렬되지 않은 정수 배열에서 k번째로 큰 원소를 찾는 알고리즘 문제입니다. 예를 들어 [3,2,1,5,6,4]에서 k=2일 경우 결과는 5가 됩니다.

접근법 1: 최소 힙 활용

크기가 k인 최소 힙을 유지하면 효율적으로 해결할 수 있습니다. 힙의 루트는 항상 현재까지 본 원소 중 k번째로 큰 값이 됩니다.

class KthElementFinder {
    public int findKthLargest(int[] arr, int targetRank) {
        // Java의 PriorityQueue는 기본적으로 최소 힙
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int num : arr) {
            minHeap.add(num);
            
            // 힙 크기가 k를 초과하면 최소값 제거
            if (minHeap.size() > targetRank) {
                minHeap.remove();
            }
        }
        
        // 힙에 남은 k개 중 가장 작은 값이 정답
        return minHeap.element();
    }
}

시간 복잡도: O(n log k), 공간 복잡도: O(k)

접근법 2: 내장 정렬 활용

가장 직관적인 방법으로, 전체 정렬 후 인덱스로 접근합니다.

import java.util.Arrays;

class SimpleSolver {
    public int getKthLargest(int[] data, int k) {
        // 오름차순 정렬
        Arrays.sort(data);
        // 뒤에서 k번째 원소 반환
        return data[data.length - k];
    }
}

시간 복잡도: O(n log n) — 간단하지만 대규모 데이터에 비효율적

접근법 3: 퀵셀렉트 알고리즘

퀵정렬의 분할 개념을 용한 선택 알고리즘으로, 평균 O(n) 시간에 동작합니다.

class QuickSelectSolver {
    public int findKthLargest(int[] nums, int k) {
        // k번째 큰 값 = (n-k)번째 작은 값의 인덱스
        int targetIndex = nums.length - k;
        return select(nums, 0, nums.length - 1, targetIndex);
    }
    
    private int select(int[] arr, int start, int end, int targetIdx) {
        if (start == end) {
            return arr[start];
        }
        
        int pivotPos = partition(arr, start, end);
        
        if (targetIdx == pivotPos) {
            return arr[pivotPos];
        } else if (targetIdx < pivotPos) {
            return select(arr, start, pivotPos - 1, targetIdx);
        } else {
            return select(arr, pivotPos + 1, end, targetIdx);
        }
    }
    
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int storeIdx = low;
        
        for (int i = low; i < high; i++) {
            if (arr[i] < pivot) {
                swap(arr, storeIdx, i);
                storeIdx++;
            }
        }
        
        swap(arr, storeIdx, high);
        return storeIdx;
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

최악의 경우 O(n²)이지만, 랜덤 피벗 선택이나 중간값 중의 중간값 기법으로 개선 가능합니다.

접근법 비교

실전 팁

• k가 매우 작을 때: 최소 힙 방식이 메모리 효율적
• 배열을 수정할 수 없을 때: 퀵셀렉트는 복사본이 필요하거나 별도 공간 사용
• 여러 쿼리 처리 시: 한 번 정렬 후 재활용