[Coding Test Bookmark]디스크 스케줄링(java, 프로그래머스)

문제 설명

 

운영 체제는 CPU 스케줄링을 위해 여러 작업을 처리해야 합니다. 작업이 먼저 요청된 순서가 아닌, 작업의 소요 시간이 짧은 순서대로 처리할 경우, 평균 대기 시간을 줄일 수 있습니다. 작업이 요청되는 시각과 소요 시간이 주어질 때, 모든 작업의 평균 대기 시간을 최소화하는 알고리즘을 작성하세요.

입력 설명

작업은 [요청 시각, 소요 시간] 형태로 배열에 담겨 있으며, 총 N개의 작업이 주어집니다.

• 각 작업은 [요청 시각, 소요 시간] 형태입니다.
• 작업이 하나씩 처리되며, 작업이 끝날 때까지 CPU는 다른 작업을 수행하지 않습니다.
• 작업의 요청 시각과 소요 시간은 0 이상 1000 이하입니다.
• 작업 개수는 1 이상 100 이하입니다.

입출력 예시

 

입력 : [[0, 3], [1, 9], [2, 6]]

출력 : 9

설명 :

- 첫 번째 작업은 0초에 요청되어 3초 후인 3초에 완료됩니다.

- 두 번째 작업은 1초에 요청되어 9초가 걸리므로, 3초부터 시작해서 12초에 완료됩니다.

- 세 번째 작업은 2초에 요청되어 6초가 걸리므로, 12초부터 시작해서 18초에 완료됩니다.

총 대기 시간 = (3 - 0) + (12 - 1) + (18 - 2) = 9 + 11 + 16 = 36

평균 대기 시간 = 36 / 3 = 12

 

Java

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 소요 시간이 짧은 순으로 정렬
        int currentTime = 0; // 현재 시간
        int totalWaitTime = 0; // 총 대기 시간
        int jobIndex = 0; // jobs 배열을 순회할 인덱스
        int completedJobs = 0; // 완료된 작업 개수

        while (completedJobs < jobs.length) {
            while (jobIndex < jobs.length) {
                pq.offer(jobs[jobIndex]);
                jobIndex++;
            }

            if (pq.isEmpty()) {
                // 처리할 작업이 없으면 시간을 앞으로 이동
                currentTime = jobs[jobIndex][0];
            } else {
                // 처리 가능한 작업이 있다면 소요 시간이 가장 짧은 작업부터 처리
                int[] job = pq.poll();
                currentTime += job[1]; // 작업을 처리하는데 걸린 시간만큼 현재 시간 증가
                totalWaitTime += currentTime - job[0]; // (종료 시각 - 요청 시각)을 대기 시간에 추가
                completedJobs++;
            }
        }

        return totalWaitTime / jobs.length;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] jobs = { {0, 3}, {1, 9}, {2, 6} };
        System.out.println(sol.solution(jobs));
    }
}