[백준 1927번] [Kotlin] 최소 힙

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

난이도 : 실버 2
태그 : 자료 구조, 우선순위 큐

 

 

설명

최소 힙을 사용하여

1. 배열에 자연수 x를 넣고

2.가장 작은 값을 출력후 배열에서 제거

하는 프로그램을 만드는 문제입니다.

 

자바와 코틀린에는 기본적으로 지원되는 PrioryQueue 자료구조가 있습니다.

말 그대로, 우선순위에 따라 하나씩 꺼내올 수 있는 큐 인데요.

만약 1, 3, 5, 2, 0, 10 순으로 넣었다면

꺼낼 때에는 값에 따라 우선순위를 부여해 0, 1, 2, 3, 5, 10 순으로 꺼내게 됩니다.

 

소스코드

import java.util.*

fun main() {
    val n = readLine()!!.toInt()

    val pq = PriorityQueue<Int>()

    repeat(n) {
        val num = readLine()!!.toInt()
        if (num == 0) {
            if (pq.isEmpty()) {
                println(0)
            } else {
                println(pq.poll())
            }
        } else {
            pq.offer(num)
        }
    }
}

 

 

후기

우선순위 큐는 최소/최대 힙 말고도 아주 많은 곳에 쓰이니 알아두면 좋은 자료구조 입니다.