99클럽 코테 스터디 10일차 TIL Kth Largest Element in a Stream

# 오늘의 학습 키워드 

힙

 

# 오늘의 문제 

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.

 

# 나의 풀이방식 

class KthLargest {

    private 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();
    }

}

 

 

# 오늘의 공부 

 

1. 힙(Heap) 이란?

- 데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전이진트리(Complete Binary Tree)

 

2. 완전이진트리(Complete Binary Tree)란?

- 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 

 

3. 인덱스 구하는 방법 

- 부모 노드 인덱스 번호 = 자식 인덱스 번호 / 2

- 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2

- 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1 

 

4. PriorityQueue 선언

-오름차순 : PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

-내림차순 :  PriorityQueue priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

5. PriorityQueue 삽입 

-add()

-offer()

 

6. PriorityQueue 삭제

-clear() : 모든 요소 삭제

-poll() : head 요소 조회 및 삭제, 큐가 비어있으면 null 반환

 

7. PriorityQueue 조회

-peak() : head 요소 반환, 큐가 비어있으면 null 반환

 

# 오늘의 회고 

  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

  - 어떻게 해결했는지

  - 무엇을 새롭게 알았는지

  - 내일 학습할 것은 무엇인지

 

배열 문제가 나오면 for문으로 문제푸는 방법만 떠올렸었는데 어떤 경우에 stack으로 풀고 heap을 이용해서 풀어야하는지 파악하는게 중요한것 같다.

평소에 heap에 대한 개념이 없어서 이번 문제를 풀면서 heap이 최소/최대값을 구할때 priorityQueue를 이용해서 푸는게 for문으로 정렬하면서 푸는것보다 시간복잡도 측면에서 효율적이라는 점을 알게 되었다.