[코딩테스트 - 10일차] Kth Largest Element in a Stream

반응형

[문제]

 

주어진 정수 배열에서 k번째로 높은 점수를 찾는 문제로 새로운 점수가 추가될 때마다 k번째로 높은 점수를 반환해야 한다

ex.
입력:
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
출력 : [null, 7, 7, 7, 8]

 

[풀이]

import java.util.PriorityQueue;

class KthLargest {
    public PriorityQueue<Integer> queue;
    public int k;
    public KthLargest(int k, int[] nums) {
        //초기화 하기
        this.k = k;
        queue = new PriorityQueue<>();
        
        for(int i=0;i<nums.length;i++){
            add(nums[i]);
        }
    }
    
    public int add(int val) {
        queue.offer(val);
        if(queue.size()>k){ //k보다 사이즈 크면 값 빼기
            queue.poll();
        }
        return queue.peek();
    }
}

[개념 정리]

1. 우선순위 큐(Priority Queue)와 힙(Heap)

 

우선순위 큐(Priority Queue)

- 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고 우선순위가 가장 높은 데이터가 먼저 나오는 자료구조.

- 모든 항목에는 우선순위가 있으며, 우선순위가 높은 요소는 낮은 요소보다 먼저 Queue에서 제외된다.

- 두 요소의 우선순위가 같으면 Queue의 순서에 따라 제공된다.

- 대표적인 구현 방식으로 힙(Heap)을 이용한다.

 

힙(Heap)

- 이진 힙(bnary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내기 위한 완전 이진 트리 형태로 만들어진 자료구조이다.

* 최대힙(Max Heap): 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같을 때. 루트 노드 = 트리의 최댓값

* 최소힙(Min Heap): 부모 노드의 값은 항상 자식노드보다 작거나 같을 때. 루트 노드 = 트리의 최솟값

- 이를 통해 최댓값과 최솟값을 빠르게 찾아낼 수있으며, 삽입, 삭제 연산시에도 부모 노드가 자식 노드보다 우선순위만 높으면 되므로 결국 트리의 깊이만큼만 비교하면 되기 때문에 빠르게 수행 가능하다.

 

3) 우선순위 큐 선언

// 기본적으로 낮은 수가 우선순위를 가짐
PriorityQueue<Integer> queue = new PriorityQueue<>();

// 높은 수가 우선순위를 가지려면 Collections.reverseOrder() 사용
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

// 문자 > 알파벳 순으로 더 빨리오는 문자열이 우선순위를 가짐
PriorityQueue<String> queue = new PriorityQueue<>();

 

4) 우선순위 큐 메서드

public boolean add(E e) // 삽입 (성공 시 true / 실패 시 IllegalstateException 발생)

public E element() // 삭제 없이 요소 읽어옴(peek()과 달리 비었을 때 NoSuchElementException 발생)

public boolean offer(E e) // 객체 저장(성공 시 true / 실패 시 false)

public E peek() // 삭제 없이 요소 읽어옴(비어있을 시 null 반환)

public E poll() // 객체 꺼내서 반환(비어있을 시 null 반환)

public boolean remove(Object o) // 객체 꺼내서 반환(비어있을 시 NoSuchElementException 발생)

public boolean contains(Object o) // 찾고자하는 요소 있는지 확인할 때

size() // 큐에 있는 요소 개수 반환

isEmpty() // 비어있는지 확인

 

 

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