[Programmers] 디스크 컨트롤러

🔒 문제

🧠 아이디어

나는 다음 최소힙 2개의 우선순위 큐를 사용했다.
(1) 최소 작업 소요시간을 기준으로한 우선순위 큐
(2) 작업 요청 시간 기준으로한 우선순위 큐

(2)의 우선순위 큐를 생성하는 대신 대신 jobs 를 오름차순으로 미리 정렬해두고 풀이해도 괜찮다.

🔑 Kotlin Code

import java.util.*

class Solution {
    fun solution(jobs: Array<IntArray>): Int {
        // 작업 소요시간 짧은 -> 요청 시간 먼저 오름차순
        val jobCostPQ = PriorityQueue<IntArray>(1_000){ arr1, arr2 ->
            if (arr1[1] == arr2[1]) arr1[0].compareTo(arr2[0])
            arr1[1].compareTo(arr2[1])
        }
        // 요청 시간 먼저 -> 작업 소요시간 적은
        val reqTimePQ = PriorityQueue<IntArray>(1_000){ arr1, arr2 ->
            if (arr1[0] == arr2[0]) arr1[1].compareTo(arr2[1])
            arr1[0].compareTo(arr2[0])
        }

        for (job in jobs) reqTimePQ.add(job)

        var currentTime = 0
        var waitTime = 0

		// 모든 큐가 비어있을 때까지 작업 실행
        do {
        	// 현재 처리할 작업이 없으면 다음 작업 요청이 들어오는 시점으로 현재시점 이동.
            if (reqTimePQ.isNotEmpty() && jobCostPQ.isEmpty() && currentTime < reqTimePQ.peek()[0]) currentTime = reqTimePQ.peek()[0]
            // 현재 시점 기준 요청받은 작업 우선순위 큐에 추가
            while (reqTimePQ.isNotEmpty() && currentTime >= reqTimePQ.peek()[0]) jobCostPQ.add(reqTimePQ.poll())
            val (reqTime, taskTime) = jobCostPQ.poll()
            currentTime += taskTime
            waitTime += (currentTime - reqTime)
        } while (jobCostPQ.isNotEmpty() || reqTimePQ.isNotEmpty())


        return waitTime / jobs.size
    }
}