【프로그래머스】 힙 - 디스크 컨트롤러 (Kotlin)

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

 

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

 

이때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

 

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

 

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간]입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

 

입출력 예

jobs	return
[[0, 3], [1, 9], [2, 6]]	9

 

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

 

---

풀이

\(n\)개의 작업이 연속으로 실행된다고 가정하자.

\(1\) 이상 \(n\) 이하인 정수 \(i\)에 대해 \(i\)번째 작업이 요청된 시점을 \(r_i\), 수행 시간을 \(t_i\)라 하면

\(i\)번째 작업은 앞 \(i-1\)개의 작업을 순차적으로 수행하고 나서 시작되므로 요청부터 종료까지 걸린 시간은 다음과 같다.

\(i\)번째 작업이 요청되고 종료되기까지 걸리는 시간
= 시작 시점 - 요청 시점 + 수행 시간
= \(r_1 + \sum_{k = 1} ^ {i - 1} {t_k} - r_i + t_i\)
= \(r_1 - r_i + \sum_{k = 1} ^ {i} {t_k}\)

 

각 \(i\)에 대한 위 값을 모두 더하면 다음과 같다.

 

$$ nr_1 - \sum_{k = 1}^{i} {r_k} + \sum_{k = 1}^{n} {(n - k + 1)t_k} $$

 

먼저 수행되는 작업일수록 수행 시간이 전체 값에 영향을 많이 미친다는 것을 알 수 있다.

따라서 평균을 최소화하려면 수행 시간이 짧은 작업을 우선하여 수행해야 한다.

 

먼저 힙을 2개 준비한다. 현재 수행할 수 없는 작업이 담긴 waiting과 현재 수행할 수 있는 작업이 담긴 runnable이다.

시간을 경과시키면서 waiting에서 수행할 수 있는 작업을 runnable로 옮긴 다음, runnable에서 수행 시간이 가장 짧은 작업을 꺼내서 요청부터 종료까지 걸린 시간을 계산할 것이다. waiting은 현재 시점 이전에 요청된 작업을 꺼내기 편하도록 요청 시점을 기준으로 오름차순 정렬할 것이고, runnable은 수행 시간을 기준으로 오름차순 정렬할 것이다.

 

현재 시점을 나타내는 변수 time과 요청부터 종료까지 걸린 시간의 합을 나타내는 변수 sum도 선언한다.

val waiting = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
val runnable = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
var sum = 0
var time = 0

 

jobs에 담긴 모든 작업을 waiting에 추가한다. IntArray가 아니라 Pair를 사용했다.

for (job in jobs) {
    waiting.offer(job[0] to job[1])
}

 

이제 반복 작업 로직을 작성한다.

먼저 waiting에서 현재 시점 이전에 요청된 모든 작업을 꺼내어 runnable에 추가한다.

waiting은 요청 시점 기준으로 정렬되어 있으므로 요청 시점이 현재 시점 이후인 작업을 만날 때까지 계속 꺼내면 된다.

반복하는 동안 waiting이 비게 될 수 있으므로 NullPointerException을 방지하기 위해 waiting이 비어있지 않다는 조건이 필요하다.

while (waiting.isNotEmpty() && waiting.peek().first <= time) {
    runnable.offer(waiting.poll())
}

 

수행할 작업이 남아있지만 당장 수행하지 못할 때, 즉 waiting이 비어있지 않지만 runnable이 비어있을 때는 남은 작업들 중 가장 빨리 수행할 수 있는 작업의 요청 시점으로 time을 건너뛴다.

if (waiting.isNotEmpty() && runnable.isEmpty()) {
    time = waiting.peek().first
    continue
}

 

runnable이 비지 않았다면 수행 시간이 가장 짧은 작업을 꺼낸다.

요청부터 종료까지 걸린 시간(= 현재 시점 - 요청 시점 + 수행 시간)을 계산하여 sum에 더한다.

수행 시간만큼 시간이 경과하므로 time에 수행 시간을 더한다.

val job = runnable.poll() 
sum += time - job.first + job.second
time += job.second

 

위 과정을 while문을 사용하여 모든 작업이 종료될 때까지 반복되어야 한다.

waiting 또는 runnable이 비지 않았다면 작업이 모두 완료되지 않은 것이다.

따라서 while문의 조건식은 waiting.isNotEmpty() || runnable.isNotEmpty()이다.

 

마지막으로 sum을 jobs의 크기로 나눈 값을 리턴한다.

 

코드

fun solution(jobs: Array<IntArray>): Int {
    val waiting = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    val runnable = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    var sum = 0
    var time = 0

    // 수행해야 하는 모든 작업을 waiting에 추가
    for (job in jobs) waiting.offer(job[0] to job[1])

    while (waiting.isNotEmpty() || runnable.isNotEmpty()) {
        // 바로 시작할 수 있는 모든 작업을 runnable에 추가
        while (waiting.isNotEmpty() && waiting.peek().first <= time) {
            runnable.offer(waiting.poll())
        }

        // 수행할 작업이 남아 있지만 바로 시작할 수 없다면 시간을 다음 작업의 요청 시점까지 건너뜀
        if (waiting.isNotEmpty() && runnable.isEmpty()) {
            time = waiting.peek().first
            continue
        }

        // 수행 시간이 가장 짧은 작업을 꺼냄
        val job = runnable.poll()

        // 현재 시점 - 작업의 요청 시점 + 작업의 수행 시간을 sum에 더함
        sum += time - job.first + job.second
        // 작업의 수행 시간만큼 시간이 경과
        time += job.second
    }

    // 평균을 리턴
    return sum / jobs.size
}