Kotlin 코딩테스트의 Kick! 우선순위큐 (Priority Queue)

알고리즘 공부를 하면서 은근 자주 쓰게 되는 기능. 우선순위 큐 ~!

어떤 것일까?

우선순위 큐 (Priority Queue)

• 우선순위가 높은 요소부터 꺼내는 자료 구조
• 기본적으로 힙(Heap) 구조를 사용하여 내부적으로 요소들을 정렬

✅ 특징

• 자동 정렬
  • 요소를 add()하면 우선순위가 높은 순서로 정렬됨.
  • 하지만 poll()을 호출할 때까지 정렬된 상태는 아니며, 꺼낼 때 우선순위에 따라 자동으로 정렬됨.
• 우선순위 기반
  • 우선순위가 높은 요소를 먼저 처리하며, 기본적으로 최소 힙(Min-Heap)을 사용.
  • 즉, 가장 작은 값을 우선적으로 꺼냄.
  • 최대 힙(Max-Heap)을 사용하려면 Comparator를 설정해야함
• 삽입 시간
  • add() 또는 offer()는 O(log n) 시간 복잡도
• 꺼내는 시간
  • poll()은 O(log n) 시간 복잡도

✅ 기본 동작 (최소 힙)

기본적으로 PriorityQueue는 최소 힙(Min-Heap)을 사용하여 가장 작은 값부터 꺼다.

kotlin
복사편집
import java.util.PriorityQueue

fun main() {
    val pq = PriorityQueue<Int>()
    pq.add(5)
    pq.add(1)
    pq.add(3)

    println(pq.poll()) // 1 (가장 작은 값)
    println(pq.poll()) // 3
    println(pq.poll()) // 5
}

위 예제에서 PriorityQueue는 기본적으로 가장 작은 값부터 꺼낸다.

✅ 최대 힙 사용 (내림차순 정렬)

Comparator를 사용하면 최대 힙(Max-Heap)을 사용할 수 있다. 이 경우 가장 큰 값을 먼저 꺼낸다.

import java.util.PriorityQueue

fun main() {
    val pq = PriorityQueue<Int>(compareByDescending { it }) // 내림차순 정렬
    pq.add(5)
    pq.add(1)
    pq.add(3)

    println(pq.poll()) // 5 (가장 큰 값)
    println(pq.poll()) // 3
    println(pq.poll()) // 1
}

위 예제에서는 compareByDescending { it }을 사용하여 내림차순(가장 큰 값을 먼저 꺼내는) 우선순위 큐를 만들어

역순으로 출력하여 가장 큰 값을 꺼낸다.