[백준 알고리즘/Kotlin] 1715번 카드 정렬하기 (feat. 우선순위 큐, PriorityQueue 클래스와 메서드)
1. 로직 작성하기
1-1. 로직 오해하기
저는 주어진 카드 묶음의 수를 오름차순으로 정렬하고, 앞에 오는 두 수부터 차근차근 더해가면 될 것이라고 생각했습니다.
5
4
4
5
9
10
위와 같은 입력이 주어졌을 경우
1. 배열에 담아 [4, 4, 5, 9, 10]
2. 배열을 오름차순 정렬하고 [4, 4, 5, 9, 10]
3. 앞에 있는 두 수부터 더한다고 생각했습니다. (4 + 4) + (8 + 5) + (13 + 9) + (22 + 10) = 75
1-2. 로직 다시 체크하기
그러나 이 문제는 항상 가장 작은 두 수를 찾아, 더해야 하는 문제입니다.
5
4
4
5
9
10
위와 같은 입력이 주어졌을 경우
1. 배열에 담아
cards = [4, 4, 5, 9, 10]
2. 가장 작은 두 수를 찾아 빼고, 그 두 수를 더한 뒤, 다시 배열에 넣어줍니다.
cards = [5, 9, 10]
sum = 4 + 4
result += 8
cards = [5, 9, 10, 8]
(반복)
3. 가장 작은 두 수를 찾아 빼고, 그 두 수를 더한 뒤, 다시 배열에 넣어줍니다.
cards = [9, 10]
sum = 5 + 8
result += 13
cards = [9, 10, 13]
4. 가장 작은 두 수를 찾아 빼고, 그 두 수를 더한 뒤, 다시 배열에 넣어줍니다.
cards = [13]
sum = 9 + 10
result += 19
cards = [13, 19]
5. 가장 작은 두 수를 찾아 빼고, 그 두 수를 더한 뒤, 다시 배열에 넣어줍니다.
cards = []
sum = 13 + 19
result += 32
cards = [32]
6. 배열의 길이가 1이므로 종료
결과적으로 result = 72 (위에 나왔던 결과와 다릅니다. 72가 옳은 결과입니다.)
즉, 우리는 이 문제를 풀어내기 위해 우선순위 큐를 사용해야 한다는 것입니다.
⚙️ 2. 우선순위 큐
큐(Queue)에서 데이터를 꺼낼 때 일반적인 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First-In-First-Out) 구조이지만,
우선순위 큐는 데이터가 들어올 때마다 우선순위에 따라 정렬되어 있어 가장 높은 우선순위의 데이터가 먼저 나가는 특징이 있습니다.
Kotlin에서는 PriorityQueue 클래스를 사용하여 우선순위 큐를 구현할 수 있습니다.
우선순위 큐 PriorityQueue는 기본적으로 작은 값이 높은 우선순위를 가지는 최소 힙 구조입니다.
저희가 작성해둔 로직(1-2)에 바로 사용할 수 있겠군요.
2-1. PriorityQueue의 함수
어떤 메서드가 있는지 확인해보고 넘어가겠습니다.
| 순번 | 설명 | 메서드 | 비고 |
| 1 | 단일 요소 추가 | add(e) | 공간이 부족할 경우 IllegalStateException (오류) |
| 2 | 단일 요소 추가 | offer(e) | 공간이 부족할 경우 false (코드는 계속 실행) |
| 3 | 가장 우선순위가 높은 요소 확인 | peek() | |
| 4 | 가장 우선운위가 높은 요소 제거 및 반환 | poll() | |
| 5 | 주어진 요소 제거 | remove(e) | 동일한 요소가 여러 개 존재할 경우 하나만 제거 |
| 6 | 큐가 비어 있는지 여부 확인 | isEmpty() | |
| 7 | 큐의 크기 반환 | size |
2-2. 우선순위를 변경할 수도 있나요?
그렇습니다. PriorityQueue는 작은 값이 우선순위를 가지지만 커스텀을 통해 우선순위를 변경할 수 있습니다.
기본형 (정수형 우선순위 큐, 작은 값이 우선순위를 가진다.)
import java.util.PriorityQueue
fun main() {
val priorityQueue = PriorityQueue<Int>()
priorityQueue.add(3)
priorityQueue.add(1)
priorityQueue.add(4)
priorityQueue.add(2)
while (priorityQueue.isNotEmpty()) {
println(priorityQueue.poll())
}
}
정수형 우선순위 큐 (큰 값이 우선순위를 가진다.)
import java.util.PriorityQueue
fun main() {
val maxHeap = PriorityQueue<Int>(compareByDescending { it })
maxHeap.offer(5)
maxHeap.offer(2)
maxHeap.offer(8)
while (maxHeap.isNotEmpty()) {
println(maxHeap.poll())
}
}
문자형 우선순위 큐 (길이가 짧은 값이 우선순위를 가진다.)
import java.util.PriorityQueue
fun main() {
val minHeap = PriorityQueue<String>(compareBy { it.length })
minHeap.offer("apple")
minHeap.offer("banana")
minHeap.offer("kiwi")
while (minHeap.isNotEmpty()) {
println(minHeap.poll())
}
}
3. 결과 코드
그렇다면 위에서 찾아본 우선순위 큐를 통해 코드를 작성해보도록 하겠습니다.
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val n = br.readLine().toInt()
val cards = PriorityQueue<Long>()
repeat(n) {
cards.add(br.readLine().toLong())
}
// 결과 : result, 카드 정렬한 횟수
var result = 0L
while (cards.size > 1) {
val sum = cards.poll() + cards.poll()
result += sum
cards.add(sum)
}
println(result)
br.close()
}
1-2에 정리한 로직 그대로 작성해봤는데요. (글로 작성한 것이 이렇게 짧아진다는 것... 짜릿하네요.)
우선순위 큐를 꼭 기억하고 있어야 겠습니다 😆