[Kotlin] 백준 17612 : 쇼핑몰

문제 링크 : https://www.acmicpc.net/problem/17612

문제 해설

일종의 정렬 문제. 계산대를 우선순위 큐로, 빠져나온 고객을 리스트로 생각해볼 수 있다.

 

고객을 정렬해야 하니 고객 정보를 어떻게 할지 생각해보자. 각각의 고객은 회원번호와 계산해야 할 물건의 개수를 갖고 있다. 그리고 계산해야 할 물건의 개수는 계산에 걸리는 시간과 같다.

 

우선 계산대에 들어가는 순서부터 생각해보면 가장 시간이 적게 걸리는 계산대에 먼저 들어가고, 같은 시간이 걸리는 계산대는 번호가 빠른곳부터 들어가게 된다. 모든 고객은 계산대에 들어가게 되니 각 고객 번호와 계산에 걸리는 시간에 더불어 들어간 계산대 번호를 속성으로 넣어주고, 시간과 계산대 번호를 정렬 기준으로 정해준다.

private class Customer(val id: Int, val time: Int, val counter: Int) : Comparable<Customer> {
    override fun compareTo(other: Customer) = if (time == other.time) counter - other.counter else time - other.time
}

계산대는 수시로 정렬을 해야하니 우선순위 큐로 선언한다.

 

처음에는 계산대가 모두 비어있으니 계산대의 개수만큼 손님들을 계산대에 채워넣는다. 이 때 전체 고객의 수가 계산대의 수보다 적을 수 있기 때문에 \(n\)과 \(k\)중 더 작은 값만큼 계산대에 손님을 채워넣는다.

val counters = PriorityQueue<Customer>()
repeat(minOf(n, k)) {
    StringTokenizer(readLine()).apply { counters.add(Customer(nextToken().toInt(), nextToken().toInt(), it)) }
}

 

모든 계산대에 손님을 채워넣었으니 이후 동작을 구현해보자.

 

남은 고객들을 계산대에 채워넣어야 하는데 계산대는 시간과 계산대 번호를 기준으로 한 우선순위 큐로 구현되어 있다. 즉, 우선순위 큐의 최상단에 있는 정보가 다음 고객이 들어갈 계산대의 정보가 된다.

 

따라서 우선순위 큐의 끝부분을 꺼내고 해당 카운터에 다음 고객을 추가하면 된다. 이 때 계산대 밖으로 나온 고객을 나온 순서대로 정렬해야 하기 때문에 다음 고객을 추가할 때는 이전 고객(= 우선순위 큐에서 꺼내진 고객)이 계산하는데 걸린 시간을 현재 고객이 계산하는데 필요한 시간에 더해주고 이전 고객의 계산대 번호를 사용해서 추가해준다.

 

계산대에서 나온 고객은 같은 시간에 나올 경우 계산대 번호가 큰 고객부터 나오기 때문에 Customer 클래스에서 정의한 compareTo()로는 정렬할 수 없다.

 

이를 해결하려면 계산대에서 나온 고객을 따로 정렬해야 하는데, 이를 위해 계산대에서 나온 고객을 저장할 리스트를 별도로 선언한 후 우선순위 큐에서 꺼낸 고객을 리스트에 추가해준다.

val exitCustomer = ArrayList<Customer>()
for (i in k + 1..n) {
    counters.poll().apply {
        exitCustomer.add(this)
        StringTokenizer(readLine()).apply { counters.add(Customer(nextToken().toInt(), time + nextToken().toInt(), counter)) }
    }
}

모든 고객이 계산대에서 나오거나 계산대에 들어가있으니 계산대에 남아있는 고객을 내보낸다.

repeat(counters.size) { exitCustomer.add(counters.poll()) }

마지막으로 매장에서 나온 고객을 시간순 → 계산대 번호가 큰 순서로 정렬한 후 모든 고객들에 대해 매장에서 나온 순서\(\times\)회원번호의 합계를 계산하여 출력한다.

 

이 때 결과가 Int 범위를 초과할 수 있기 때문에 Long 타입으로 계산한다.

exitCustomer.sortWith(compareBy({ it.time }, { -it.counter }))
var result = 0L
exitCustomer.forEachIndexed { i, customer -> result += customer.id * (i + 1L) }
println(result)

Code

import java.util.StringTokenizer
import java.util.PriorityQueue

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(' ').map { it.toInt() }
    val counters = PriorityQueue<Customer>()
    repeat(minOf(n, k)) {
        StringTokenizer(readLine()).apply { counters.add(Customer(nextToken().toInt(), nextToken().toInt(), it)) }
    }
    val exitCustomer = ArrayList<Customer>()
    for (i in k + 1..n) {
        counters.poll().apply {
            exitCustomer.add(this)
            StringTokenizer(readLine()).apply { counters.add(Customer(nextToken().toInt(), time + nextToken().toInt(), counter)) }
        }
    }
    repeat(counters.size) { exitCustomer.add(counters.poll()) }
    exitCustomer.sortWith(compareBy({ it.time }, { -it.counter }))
    var result = 0L
    exitCustomer.forEachIndexed { i, customer -> result += customer.id * (i + 1L) }
    println(result)
}

private class Customer(val id: Int, val time: Int, val counter: Int) : Comparable<Customer> {
    override fun compareTo(other: Customer) = if (time == other.time) counter - other.counter else time - other.time
}