[코테 스터디 10일차 TIL] Kth Largest Element in a Stream

dev_jubby·2024년 7월 31일

Java TIL heap 개발자취업 코딩테스트

코테스터디

목록 보기

10/36

💛 오늘의 학습 키워드

[힙(Heap)] Kth Largest Element in a Stream

📝 문제

문제 설명

Design a class to find the $k^{th}$ largest element in a stream. Note that it is the $k^{th}$ largest element in the sorted order, not the $k^{th}$ 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 $k^{th}$ largest element in the stream.

제한 조건

1 <= k <= $10^4$
0 <= nums.length <= $10^4$
$-10^4$ <= nums[i] <= $10^4$
$10^4$ <= val <= $10^4$
At most $10^4$ 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 $k^{th}$ element.

입출력 예

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

💬 내 풀이

class KthLargest {
     // 우선순위 큐 선언
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    int size = 0;

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

        // nums[] 을 우선순위 큐에 넣고, 큐보다 k값이 크면 마지막 요소 제거
        for (int n : nums) {
            pq.offer(n);
            if(pq.size() > k) pq.poll();
        }
    }

    public int add(int val) {
        // val 값을 우선순위 큐에 추가
        pq.offer(val);
        if(pq.size() > size) pq.poll();
        return pq.peek();
    }
}

💻 내 접근 방법

먼저 우선순위 큐 객체를 생성한다.
- PriorityQuere : 일반적인 큐의 구조(FIFO)를 가지면서, 우선순위를 먼저 결정하고, 높은 데이터가 먼저 나가는 자료구조이다.

우선순위 큐 선언

// 높은 우선순위의 요소를 먼저 처리하는 큐 선언
PriorityQuere<Integer> pq = new PriorityQueue<>(); 
// 낮은 우선순위의 요소를 먼저 처리하는 큐 선언
PriorityQuere<Integer> pq = new PriorityQueue<>()Collections.reverseOrder();

k번째로 큰 요소를 꺼내기 위해 size를 전역변수로 선언한다.
KthLargest() 에서는 k를 size에 넣어주고, nums[] 데이터를 pq에 넣어준다.
- 여기서 k 보다 pq의 크기가 크면 poll() 메소드를 사용해서 큰 숫자부터 삭제하여 k와 pq의 크기가 항상 같게 만들어준다.
add() 는 똑같이 offer()를 사용하여 val 값을 추가한 후 동일하게 큰 요소는 삭제한다.
k번째로 큰 요소를 꺼내기 위해 peek() 메소드를 사용하여 꺼내어 return 한다.

✨ 다른 사람 풀이

class KthLargest {
    private static int k;
    private PriorityQueue<Integer> heap;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        heap = new PriorityQueue<>();
        
        for (int num: nums) {
            heap.offer(num);
        }
        
        while (heap.size() > k) {
            heap.poll();
        }
    }
    
    public int add(int val) {
        heap.offer(val);
        if (heap.size() > k) {
            heap.poll();
        }

        return heap.peek();
    }
}