[ps] 디스크 컨트롤러

https://programmers.co.kr/learn/courses/30/lessons/42627#

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있다. 모든 작업의 요청부터 종료까지 소요된 시간의 평균 합이 가장 작은 경우를 구하는 것이다. 단, 작업을 수행하고 있지 않는 경우 가장 먼저 들어온 작업을 수행한다.

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

• A: 0ms에 요청되고, 3ms 소요(종료 시점: 3ms)
• B: 1ms에 요청되고, 이전 작업의 종료 시점인 3ms에 작업을 시작해서 11ms(대기 시간 2ms + 작업 시간 9ms) 소요(종료 시점: 12ms)
• C: 2ms에 요청되고, 이전 작업의 종료 시점인 12ms에 작업을 시작해서 16ms(대기 시간 10ms + 작업 시간 6ms) 소요(종료 시점: 18ms)
• 이 때 각 작업의 요청부터 종료까지 소요된 시간의 평균은 (3 + 11 + 16) / 3 = 10ms이다.

• A: 0ms에 요청되고, 3ms 소요(종료 시점: 3ms)
• C: 2ms에 요청되고, 이전 작업의 종료 시점인 3ms에 작업을 시작해서 7ms(대기 시간 1ms + 작업 시간 6ms) 소요(종료 시점: 9ms)
• B: 1ms에 요청되고, 이전 작업의 종료 시점인 9ms에 작업을 시작해서 17ms(대기 시간 8ms + 작업 시간 9ms) 소요(종료 시점:18ms)
• 이 때 각 작업의 요청부터 종료까지 소요된 시간의 평균은 (3 + 7 + 17) / 3 = 9ms이므로 이 경우가 평균합이 가장 작은 경우이다.

문제의 조건은 다음과 같다.

• 작업의 갯수는 1 이상 500 이하이다.
• 각 작업이 요청되는 시간(ms)은 0 이상 1000 이하이다.
• 각 작업의 소요 시간은 1 이상 1000 이하이다.
• 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리한다.

문제 풀이

import java.util.*;

public class Main {

    public static class Solution {

        public int solution(int[][] jobs) {
            Arrays.sort(jobs, Comparator.comparingInt(job -> job[0]));
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(job -> job[1])); // (1)

            int index = 0;
            int time = jobs[0][0];
            int answer = 0;

            while (index < jobs.length || !priorityQueue.isEmpty()) {
                while (index < jobs.length && jobs[index][0] <= time) {
                    priorityQueue.add(jobs[index++]);
                }

                if (priorityQueue.isEmpty()) {
                    time = jobs[index][0]; // (2)
                } else {
                    int[] job = priorityQueue.poll();
                    answer += time - job[0] + job[1];
                    time += job[1];
                }
            }

            return answer / jobs.length;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[][]{{24, 10}, {28, 39}, {43, 20}, {37, 5}, {47, 22}, {20, 47}, {15, 34}, {15, 2}, {35, 43}, {26, 1}});
    }

}

문제 풀이 중, 실수했던 부분을 설명하기 위해 다음과 같이 가정한다.

R: 현재 작업이 요청된 시간
P: 현재 작업의 작업 시간
X: 이전 작업의 종료 시점, X + P
T: 현재 작업의 소요 시간, X - R + P

T가 최소인 작업이 우선순위가 높다고 생각했다. 그래서 T를 최소로 만들 수 있도록 R - P가 큰 순으로 높은 우선순위로 지정했다. 하지만 X가 커지는 경우를 고려하지 않아서 틀린 생각이었다. 작업이 끝날 때마다 이전 작업의 종료 시점은 X = X + P가 되는데 두 작업의 우선순위 비교 과정에서 R - P가 크더라도 P가 더 큰 경우는 X를 더 많이 증가시키게 된다. X가 커지면 다음 작업의 T가 커지면서 전체 작업 시간의 합은 더 커질 수 있기 때문이다. 즉, P가 최소인 작업을 먼저 수행해야 R - P를 최댓값으로, X + P를 최솟값으로 만들 수 있기 때문에 P가 최소인 작업이 높은 우선순위를 가져야 한다. (1)
요청된 작업이 끝난 시점보다 이전에 요청된 작업이 하나도 없는 경우를 생각하지 못했다.(2)