[코테연습] 703. Kth Largest Element in a Stream

- 정렬 / 힙 문제

 

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/?envType=daily-question&envId=2024-08-12

 

- 문제분석

1. int[] array 숫자 중에서 k 번째에 속하는 숫자를 구하라.

2. add(int num) 을 통해서 array 에 숫자가 추가되는데, 이때에 변경되는 가장 큰 수 중 k 번째의 숫자를 리턴해라.

 

- 문제풀이

 

1. 우선순위 큐  PrioirtyQueue<Integer> 를 선언하여, array 배열에 있는 숫자를 담아. 오름차순으로 저장한다.

2. 가장 큰 k 번째의 수는 오름차순 정렬된 array 마지막 length 에서 3번째 수와 동일하다.

2-1. 우선순위 큐에서 첫번째 있는 숫자가 k 번째 수가 될 수 있도록 ( 우선순위 큐에서 가장 작은 수 ) 우선순위 큐에서 사이즈가 k 클 경우에 poll() 하여 삭제한다.

2-2. 예를 들어 [ 2, 3, 4, 5, 8 ] 숫자가 있고 k = 3 있다면, [ 4, 5, 8 ] 숫자만 우선순위 큐에 담아, 우선순위 큐 peek() 시에 k 번째로 큰 수가 출력 될 수 있도록 한다.

 

 

class KthLargest {

    int idx = 0;
    PriorityQueue<Integer> queue;
    public KthLargest(int k, int[] nums) {
        idx = k;
        queue = new PriorityQueue<Integer>();
        for (int num : nums) {
            queue.offer(num);
            if (queue.size() > idx) queue.poll();
        }
    }
    
    public int add(int val) {
        queue.offer(val);
        if (queue.size() > idx) queue.poll();
        return queue.peek();
    }
}

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