문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

당신은 대학교 입학처 소속으로, 지원자들의 최고 점수 k번째 점수를 실시간으로 주적해야한다. 이는 새로운 지원자들이 점수를 제출할때 면접 및 합격 기준 점수를 동적으로 결정하는데 도움이 된다.

주어진 정수 k에 대해 시험 점수 스트림을 유지하고, 새로운 점수가 제출된 후 k번째로 높은 점수를 지속적으로 반환하는 클래스를 구현해야 한다. 더 구체적으로 말하면, 모든 점수를 정렬한 목록에서 k번째로 높은 점수를 찾아야 한다.

KthLargest 클래스를 구현해라.

• KthLargest(int k, int[] nums)는 정수 k와 시험 점수 스트림 nums로 객체를 초기화하다.
• int add(int val)는 스트림에 새로운 시험 점수 val을 추가하고, 지금까지의 시험 점수 풀에서 k번째로 큰 요소를 반환한다.

Example

#1
Input:
["KthLargest", "add", "add", "add", "add", "add"]

[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output: [null, 4, 5, 5, 8, 8]
Explanation:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8

#2
Input:
["KthLargest", "add", "add", "add", "add"]

[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
Output: [null, 7, 7, 7, 8]
Explanation:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // return 7
kthLargest.add(10); // return 7
kthLargest.add(9); // return 7
kthLargest.add(9); // return 8

Constraints

• 0 <= nums.length <= 10^4
• 1 <= k <= nums.length + 1
• -10^4 <= nums[i] <= 10^4
• -10^4 <= val <= 10^4
• add를 최대 10^4번 호출한다.

Solved

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

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

        for(int num : nums){
            pq.offer(num);
            if(pq.size() > k) pq.poll();
        }
    }
    
    public int add(int val) {
        pq.offer(val);

        if(pq.size() > k) pq.poll();

        return pq.peek();
    }
}

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