#215 Kth Largest Element in an Array

전우재·2023년 9월 11일

leetcode

목록 보기

20/21

문제링크 - https://leetcode.com/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-interview-150

문제 조건

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
정수 배열 nums와 정수가 주어지면 배열 안에서 정수 번째로 큰 정수를 반환하면 된다.

문제 해결

문제 해결 로직

해당 문제를 해결하기 위해 최대 힙(Max Heap)을 사용한다.
- 최대 힙이란 가장 큰 요소가 항상 루트에 위치하도록 정렬하는 이진 트리.

먼저 주어진 배열을 최대 힙으로 변환하기 위해 배열로 초기화한다.
배열을 최대 힙으로 변환한다. heapify
크기 순서(입력받은 정수)만큼 힙에서 원소를 추출하여 버린다. bubbleDown
힙의 루트 노드 값을 반환한다.

데이터 입력

자료구조는 최대 힙 트리이지만, 복잡도 측면에서 이점을 얻기 위해 배열을 사용한다.

array 최대 힙 배열
n 배열의 길이

배열을 최대 힙으로 변환 (heapify)

리프노드가 아닌 최초의 노드에서 맨 끝 노드 array[n-1]의 부모인 array[(n-2)/2]에서부터 array[0]까지 heapify()를 반복한다.

    public void heapify() {
        // array[n-1] -> array[n-2] -> .. -> array[0]
        for (int i = (n - 2) / 2; i >= 0; i--) {
            bubbleDown(i, n);
        }
    }

힙 특성을 만족하도록 조정하기 (bubbleDown)

array[i]를 루트로 하는 서브 트리 array[i, i+1, .., n-1] 범위 내에서 힙 특성을 만족하도록 조정하면서 leaf 노드까지 내려간다.

leftChild와 rightChild를 비교하여 값이 더 큰 노드를 찾는다.
찾은 자식 노드와 부모 노드를 비교한다.
- 만약 부모가 더 작은 값을 가지고 있다면 부모와 자식을 교환하고 아래로 이동한다.

public void bubbleDown(int i, int n) {
        int child = 2 * i + 1; // 기본값은 leftChild
        int rightChild = 2 * i + 2;

        if (child <= n - 1) {
            // 더 큰 자식 노드를 결정합니다.
            if (rightChild <= n - 1 && array[rightChild] > array[child]) {
                child = rightChild;
            }
            // 부모가 더 작은 경우, 교환하고 아래로 이동합니다.
            if (array[i] < array[child]) {
                int temp = array[i];
                array[i] = array[child];
                array[child] = temp;

                bubbleDown(child, n);
            }
        }
    }

코드 작성

class Solution {
    private int[] array;
    private int n; // 배열의 길이

    /**
     * array[i]에서부터 시작해서 부모인 array[(i-1)/2]를 기준으로 하는 서브 트리가
     * Heap을 만족하도록 조정하면서 올라갑니다.
     *
     * @param i
     */
    public void bubbleUp(int i) {
        int child = i;
        int parent = (i - 1) / 2;

        if (parent >= 0 && array[child] > array[parent]) {
            int temp = array[child];
            array[child] = array[parent];
            array[parent] = temp;
            bubbleUp(parent);
        }
    }

    public int findKthLargest(int[] nums, int k) {
        // 최대 힙을 구성할 배열을 초기화
        array = nums;
        n = nums.length; // 배열의 길이 저장

        // 배열을 최대 힙으로 변환
        heapify();

        // k번만큼 최대 힙에서 원소를 추출하여 버림
        for (int i = 0; i < k - 1; i++) {
            int temp = array[0];
            array[0] = array[n - 1 - i];
            array[n - 1 - i] = temp;
            bubbleDown(0, n - 1 - i);
        }

        // k번째로 큰 값을 반환
        return array[0];
    }

    /**
     * array[i]를 루트(root)로 하는 서브 트리 array[i, i+1, .., n-1] 범위 내에서
     * 힙 특성을 만족하도록 조정하면서 leaf 노드까지 내려갑니다.
     *
     * @param i
     * @param n 범위의 끝 인덱스
     */
    public void bubbleDown(int i, int n) {
        int child = 2 * i + 1; // 기본값은 leftChild
        int rightChild = 2 * i + 2;

        if (child <= n - 1) {
            // 더 큰 자식 노드를 결정합니다.
            if (rightChild <= n - 1 && array[rightChild] > array[child]) {
                child = rightChild;
            }
            // 부모가 더 작은 경우, 교환하고 아래로 이동합니다.
            if (array[i] < array[child]) {
                int temp = array[i];
                array[i] = array[child];
                array[child] = temp;

                bubbleDown(child, n);
            }
        }
    }

    /**
     * 리프노드가 아닌 최초의 노드에서 맨 끝 노드 array[n-1]의
     * 부모인 array[(n-2)/2]에서부터 array[0]까지 heapify()를 반복합니다.
     */
    public void heapify() {
        // array[n-1] -> array[n-2] -> .. -> array[0]
        for (int i = (n - 2) / 2; i >= 0; i--) {
            bubbleDown(i, n);
        }
    }
}

복잡도 계산

시간 복잡도
- heapify의 경우 O(n)으로 배열의 길이에 영향을 받는다.
- k번만큼 추출하고 재구성 하는 부분의 경우 O(k*log n)을 가진다.
- 따라서 총 시간 복잡도는 O(n+klog n)이 된다.
공간 복잡도
- 공간 복잡도는 주어진 배열을 그대로 사용하기 때문에 공간 복잡도는 상수를 가진다.