[Kotlin] 백준 22234 : 가희와 은행

문제 링크

22234번: 가희와 은행

---

---

문제 해설

큐와 정렬을 적절하게 사용해서 풀 수 있는 문제이다. 문제 해결 과정은 다음과 같다.

1. 은행이 영업을 시작했을 때 대기 줄에 있는 \(N\)명의 손님을 순서대로 큐(이하 대기 큐)에 삽입한다.
2. 은행이 영업중일 때 새로 들어온 손님은 별도의 리스트(이하 신규 손님)에 \(C_x\)를 기준으로 오름차순 정렬하여 삽입한다.
   • 이 포스트에서는 손님 클래스에 Comparable을 구현한 후 우선순위 큐를 사용했다.
3. 다음 순서에 따라 \(W\)초 까지 영업을 진행한다.
   1. 대기 큐에서 손님을 한 명 꺼내어 다음 분기에 따른 계산을 진행한다. 
      • 대기 큐에서 꺼낸 손님의 \(t_x\)가 \(T\)보다 크다면  \(\min(T,\) 현재 시간 \(- W)\) 개의 줄에 \(P_x\)를 출력한 후 \(t_x\)를 \(T\)만큼 감소시키고, 현재 시간을 \(T\)만큼 증가시킨다.
      • 대기 큐에서 꺼낸 손님의 \(t_x\)가 \(T\)보다 작다면  \(\min(t_x,\) 현재 시간 \(- W)\) 개의 줄에 \(P_x\)를 출력한 후 현재 시간을 \(t_x\)만큼 증가시키고, \(t_x\)를 0으로 변경한다.
   2. 신규 손님들 중 \(C_x\)가 현재 시간 이하인 손님을 모두 대기 큐에 삽입한다.
   3. 대기 큐에서 꺼냈던 손님의 \(t_x\)가 0보다 크다면 다시 대기 큐의 마지막 삽입한다.

 

---

Code

import java.util.LinkedList
import java.util.PriorityQueue
import java.util.Queue
import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (n, t, w) = readLine().split(' ').map { it.toInt() }
    val customers: Queue<Customer> = LinkedList()
    repeat(n) {
        StringTokenizer(readLine()).apply {
            customers.add(Customer(nextToken().toInt(), nextToken().toInt(), 0))
        }
    }
    val newCustomers = PriorityQueue<Customer>().apply {
        repeat(readLine().toInt()) {
            StringTokenizer(readLine()).apply {
                add(Customer(nextToken().toInt(), nextToken().toInt(), nextToken().toInt()))
            }
        }
    }
    var currentTime = 0
    while (currentTime < w) {
        val customer = customers.poll()
        if (customer.needTime > t) {
            repeat(minOf(t, w - currentTime)) { bw.write("${customer.id}\n") }
            currentTime += t
            customer.needTime -= t
        } else {
            repeat(minOf(customer.needTime, w - currentTime)) { bw.write("${customer.id}\n") }
            currentTime += customer.needTime
            customer.needTime = 0
        }

        while (newCustomers.isNotEmpty() && newCustomers.peek().enterTime <= currentTime) {
            customers.add(newCustomers.poll())
        }

        if (customer.needTime > 0) {
            customers.add(customer)
        }
    }
    bw.close()
}

class Customer(val id: Int, var needTime: Int, val enterTime: Int): Comparable<Customer> {
    override fun compareTo(other: Customer) = this.enterTime - other.enterTime
}