[Medium] 703. Kth Largest Element in a Stream (아마존 코딩 테스트 기출 문제)

#문제 설명

Leetcode 703번문제는 int k 와 정수 array가 주어진다. 또한 이 array는 stream이기때문에 계속 정수들을 array에 추가 시킨다. 이 문제에서는 주어진 array에 여러개의 정수를 add하고, add가 끝난뒤 array에서 k번째로 큰 정수값을 반환시켜주면된다.

#문제 풀이

class KthLargest {

    private PriorityQueue<Integer> minHeap;
    private int k;
    public KthLargest(int k, int[] nums) {
        minHeap = new PriorityQueue<>();
        this.k = k;
        for(int i = 0; i < nums.length;i++){
            minHeap.add(nums[i]);
            if(minHeap.size() > k){
                minHeap.poll();
            }
        }
    }
    
    public int add(int val) {
        minHeap.add(val);   
        if(minHeap.size() > k ){
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

이 문제는 size가 k인 min-heap을 사용하면 쉽게 풀수있다. size가 k인 min heap을 쓰는 이유는 이 문제에서는 remove를 쓰지않기 때문에 k번째 이상의 element들은 필요가 없게 된다. 예를 들어 k=3과 [4,5,8,2]의 array가 주어지면, 우리는 4,5,8만 알고있으면 된다, 그리고 만약 9라는 정수를 add하게 되면 4대신 5,8,9만 가지고있는 heap를 유지하면된다. 이 단계는 min-heap를 사용하면 자연스럽게 유지되기 때문에 우리가 신경써야될 부분은 만약 heap의 size가 k보다 크게 될시에는 heap.poll()를 함으로서 heap에서 가장 작은 정수, 즉 root의 value를 poll()시키면 size가 k인 min-heap이 유지된다. 마지막은 heap.peek()을 return 함으로서 size가 k인 heap에서 가장 작은 정수 즉, array에서 k번째로 큰 정수를 return시켜주게 된다.