[99클럽 코테 스터디] 10일차 TIL 힙

 

 

오늘의 문제는 LeetCode

 

 

Kth Largest Element in a Stream

 

 

 

문제

 

 

문제 설명 

주어진 정수 배열에서 k번째로 큰 원소를 찾는 문제입니다. 여기서 k번째로 크다는 것은 인덱스가 아닌 정렬된 순서에서 k번째로 큰 원소를 의미합니다. 

 

주어진 클래스를 완성해야 합니다. 

1. kthLargest : 정수 k와 정수형 배열 nums가 매개변수로 받습니다. 예제와 같이 k와 nums가 주어졌을 때 k번째로 큰 정수를 반환하도록 stream으로 객체를 초기화 합니다. 

2. add : 정수 val이 매개변수로 주어졌을 때, 이를 배열에 추가하고 k번째로 큰 수를 반환하도록 합니다.  

 

 

 

문제 접근 및 풀이 과정

권장 풀이 시간은 60분이었으나, 저는 75분이 걸렸습니다.

리트코드 문제에 익숙하지 않아 문제를 해석하고 로직을 구성하는데 많은 시간이 소요됐습니다. 

 

 

 

문제 접근 방식

주어진 클래스가 올바른 동작을 하도록 각 클래스에 어떤 로직을 구성하는 것이 중요했습니다. 따라서 각 클래스의 매개변수를 먼저 확인하고 이를 통해 어떤 기능이 들어가야 할지를 추론할 수 있었습니다. 

 

먼저, kthLargest에서는 힙(Heap)을 사용해 k 크기만큼의 배열을 생성하고, nums 배열의 요소를 넣도록 하였습니다. 처음에는 최대힙을 사용했으나, 이후 최소힙으로 변경했습니다. 그 이유는 힙의 크기를 k로 제한하여 k번째 큰 요소를 루트 레벨에 남게 하기 위해서입니다. poll() 메서드를 사용해 nums 배열의 요소를 힙에 넣고, 힙의 크기가 k를 초과하면 루트 레벨의 요소를 제거합니다. 이렇게 하면 힙의 루트 레벨에 k번째 요소가 남게 됩니다.

 

다음으로 add 에선 정수 val 값을 힙에 추가할 것이기 때문에 먼저 힙의 크기가 k보다 큰지 작은지를 검사합니다. 만약 힙의 크기가 k보다 작은 경우, val을 그대로 요소로 추가합니다. 그렇지 않을 경우 정수 val의 값이 힙의 루트 값 보다 크다면, 루트 값을 제거하고 정수 val의 값을 힙에 추가합니다. 

 

이러한 과정을 거치면  힙의 peek() 메서드를 사용했을 때 루트 레벨의 값이 k번째 요소가 됩니다. 

 

 

문제 풀이

import java.util.PriorityQueue; 
class KthLargest {

    public  PriorityQueue<Integer> kthLargest;
    public int k; 

    public KthLargest(int k, int[] nums) {

        this.k = k;
        kthLargest = new PriorityQueue<>();

        for(int i = 0; i < nums.length; i++) {
            kthLargest.offer(nums[i]); 
            if(kthLargest.size() > k) {
                kthLargest.poll(); 
            }
        }

    }
    
    public int add(int val) {

        if(kthLargest.size() < k) {
            kthLargest.offer(val);
        } else if(val > kthLargest.peek()) {
            kthLargest.remove();
            kthLargest.offer(val);
        }
        return kthLargest.peek(); 
    }
}

 

 

this를 사용한 클래스 멤버 변수 초기화 

this.k = k; 는 생성자 매개변수 k를 클래스 멤버 변수 k에 할당하는 코드입니다. 이를 통해 클래스 멤버 변수 k가 생성자에서 전달된 값으로 초기화 됩니다. 

 

 

최대힙 vs 최소힙

최대힙은 루트를 최대값으로 갖고 최소힙은 루트에 최솟값을 갖습니다. 

여기서 최소힙을 사용하는 이유는 힙의 루트가 항상 작은 값을 갖기 때문에 k개의 요소가 남았을 때 이 중 가장 작은 값이 k번째로 큰 값이 되기 때문입니다.

 

최대 힙을 사용했을 땐 k번째로 큰 값을 찾기 위해 매번 힙을 정렬하고 k번째 값을 찾아야 합니다. 이는 비효율적이며, k번째로 큰 값을 유지하기 위해 k개의 큰 값을 저장한 후에 나머지 요소를 버리는 작업이 필요합니다. 특히, 최대힙에서는 k번째로 큰 값이 아닌 가장 큰 값이 루트에 위치하게 되므로, k번째로 큰 값을 찾기 위해 추가적인 작업이 필요합니다.

 

최소힙에서 k번째로 큰 요소를 반환하는 이유 

 

최소힙은 힙의 루트가 가장 작은 값을 유지하는 특성을 가집니다. 따라서 힙의 크기를 k로 유지함으로써 힙에는 현재까지 추가된 값 중 가장 큰 k개의 값만 남게 되는 것입니다. 

 

힙의 크기가 k일 때, 힙에 있는 k개의 요소는 현재까지 입력된 값 중 가장 큰 값들 입니다. 힙 요소 중 가장 작은 값은 k번째 요소가 되는데 그 이유는 힙의 루트가 가장 작은 값을 가지기 때문입니다. 루트보다 큰 값들이 최소 k-1개 존재하기 때문에 루트가 k번째로 큰 요소를 갖게 되고 마지막에 루트를 반환하는 것입니다. 

 

예를 들어 k값이 3이고, 초기 배열 nums가 [2, 4, 5, 8]이라고 가정합니다. 

nums에 순서대로 요소를 추가합니다. 

• 2 추가 시 힙 : [2]
• 4 추가 시 힙 : [2, 4]
• 5 추가 시 힙 : [2, 4, 5]
• 8 추가 시 힙 : 힙 사이즈가 k를 초과하기 때문에 가장 작은 요소인 2를 제거하고 8을 추가합니다. 따라서 힙에는 가장 큰 세 개 요소인 [4, 5, 8]만 남게 됩니다. 

 

 

 

 

 

이렇게 오늘 10일차 TIL을 작성해 보았습니다.