99클럽 코테 스터디 10일차 TIL | Kth Largest Element in a Stream

🛠️ 문제

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

💻 풀이

class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<>(k);

        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size()>k)minHeap.poll();     
        return minHeap.peek();
    }
}

가장 중요한 건 가장 작은값을 유지시키는 것이라 생각했다. 그래서 k를 기준으로 add에 추가 하되, 크기가 k를 초과할 경우 가장 작은 요소를 제거했다! 즉, 힙에서 루트값이 현재 스트림에서 k번째로 큰 값이라는 것.

🤔 고찰

1. PriorityQueue는 보기만 했지 처음 사용해보았다. 우선순위를 제공하는 큐인데, 우선순위에 따라 정렬됨!

2. peek와 poll의 차이점
   peek는 큐의 최상위 요소를 반환하지만 제거하지 않으며, poll은 큐의 최상위 요소를 반환하고 제거한다!