[백준 알고리즘/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에 정리한 로직 그대로 작성해봤는데요. (글로 작성한 것이 이렇게 짧아진다는 것... 짜릿하네요.)

우선순위 큐를 꼭 기억하고 있어야 겠습니다 😆