[LeetCode] 703. Kth Largest Element in a Stream - Java

https://leetcode.com/problems/kth-largest-element-in-a-stream/

Kth Largest Element in a Stream - LeetCode

---

문제

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.

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

 

Constraints:

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• At most 104 calls will be made to add.
• It is guaranteed that there will be at least k elements in the array when you search for the kth element.

---

풀이

풀이 과정

정수 k와 정수 배열 nums 배열이 주어지고 정수들을 추가할 때 k번째로 큰 숫자를 찾아내는 클래스를 구현해야 하는 문제이다.
클래스에서 구현해야하는 함수는 인스턴스를 초기화하는 함수 KthLargest와 값을 추가해주는 add이다.

해당 클래스를 구현하기 위해서 우선순위큐를 사용하도록 한다.

nums의 모든 요소와 추가되는 정수들을 우선순위큐에 담고 큐의 사이즈가 k를 초과하는 경우 마지막 요소를 제거하며 항상 k번째 큰 수가 다음에 나오도록 하는 방향으로 풀이한다.

먼저 우선순위큐와 큐의 최대 사이즈가 될 변수를 전역변수로 선언한다,

// 크기 순으로 저장할 우선순위큐 선언
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 큐에 저장할 최대 길이
int size;

 

인스턴스를 초기화 하는 함수에서는 전역변수 size에 k의 값을 저장해주고 nums 배열의 모든 요소를 큐에 저장한다.
이 때 큐의 크기가 k보다 커지게 되는 경우에는 마지막 요소를 하나 제거한다.

 public KthLargest(int k, int[] nums) {
    size = k;

    // nums 배열의 요소들을 큐에 저장
    for(int i : nums) {
        pq.offer(i);
        // 큐의 크기가 k보다 큰 경우 마지막 요소 제거
        if(pq.size() > k) pq.poll();
    }
}

 

수를 추가하는 add 함수에서는 전달받은 val값을 큐에 추가하고 마찬 가지로 길이 k를 초과하게 되는 경우에는 마지막 요소를 제거한다. 그 후 마지막에 있는 요소 값을 return 해준다.

public int add(int val) {
    // val 값을 큐에 추가
    pq.offer(val);
    // k길이를 초과하게되는 마지막 요소 제거
    if(pq.size() > size) pq.poll();

    // 마지막에 있는 요소를 return
    return pq.peek();
}

 

 

---

최종 코드

class KthLargest {
    // 크기 순으로 저장할 우선순위큐 선언
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    // 큐에 저장할 최대 길이
    int size;

    public KthLargest(int k, int[] nums) {
        size = k;
        
        // nums 배열의 요소들을 큐에 저장
        for(int i : nums) {
            pq.offer(i);
            // 큐의 크기가 k보다 큰 경우 마지막 요소 제거
            if(pq.size() > k) pq.poll();
        }
    }
    
    public int add(int val) {
        // val 값을 큐에 추가
        pq.offer(val);
        // k길이를 초과하게되는 마지막 요소 제거
        if(pq.size() > size) pq.poll();
        
        // 마지막에 있는 요소를 return
        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);
 */

---