1 | 오늘의 문제

1. Kth Largest Element

Kth Largest Element
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.

사실 이 문제를 풀지 못해서 정답을 보고 공부하는 방식으로 진행했다.

2. 알고리즘

1. 데이터 추가할 때마다 K번째 큰 요소를 유지하는 자료구조가 중요하다.
2. 그렇기에 최소 힙을 이용한다.

import java.util.PriorityQueue;

public class KthLargest {
    private int k; //1. k, 우선순위 큐는 계속 사용 -> 멤버 변수로 선언
    private PriorityQueue<Integer> minHeap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<>(k); //2. 최소 힙 선언,크기를 k로 고정

        for (int num : nums) { //3. 기존의 값을 큐에 대입
            add(num);
        }
    }

    public int add(int val) {
        minHeap.offer(val);

        // 4. 최소 힙 크기가 k를 넘어가면 첫번째 값 반환, 제거
        if (minHeap.size() > k) {
            minHeap.poll();
        }

        // 5. 루트 값(K번째 큰 수) 반환
        return minHeap.peek();
    }


    public static void main(String[] args) {
        KthLargest kthLargest = new KthLargest(3, new int[]{4, 5, 8, 2});
        System.out.println(kthLargest.add(3));   // returns 4
        System.out.println(kthLargest.add(5));   // returns 5
        System.out.println(kthLargest.add(10));  // returns 5
        System.out.println(kthLargest.add(9));   // returns 8
        System.out.println(kthLargest.add(4));   // returns 8
    }
}

최소 힙을 사용, 크기를 k로 제한하면 루트 노드가 k번째 수라는데 나는 왜 이해를 못하는가.
질문 게시판에 올려야겠다. 힙 구조를 공부하고 페이지에 추가하겠다...

+ 2024.08.01 추가

2 | 보충

1. 우선순위 큐(Priority Queue)

• 큐
  : 가장 먼저 들어온 데이터가 먼저 나가는 자료구조
  : FIFO, 한 쪽 삽입 & 한 쪽 삭제
• 우선순위 큐: 우선순위가 높은 데이터가 먼저 나가는 자료구조
• 힙 자료구조, 이진트리 구조
• 우선순위를 중요하게 다루는 상황에서 활용

2. 선언

import java.util.PriorityQueue();

//작은 수가 우선순위를 갖는다
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

3. 메서드

• add(): 원소 추가, 큐가 꽉차면 error 발생
• offer(): 원소 추가, 실패시 false 반환
• poll(): 첫번째 값 반환하고 제거, 비어있으면 null 반환
• peak(): 최대 우선 순위 요소 반환

4.

[참고]

1. 자료구조 힙
2. 우선순위 큐
3. 우선순위 큐 메서드