[프로그래머스/Java] 디스크 컨트롤러

문제

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

---

문제 파악

• jobs [작업에 요청되는 시점, 작업의 소요 시간]
• 디스크는 한번에 하나의 작업만 수행할 수 있음
• 디스크가 작업을 수행하고 있지 않은 경우, 먼저 요청이 들어온 작업부터 수행
• 시작시간과 수행시간을 고려해 수행시간의 평균이 최소가 되도록 하는 문제
• 최소 작업 우선 스케줄링 (SJF 스케줄링)

---

접근 방법

• PriorityQueue 이용
• 작업의 소요 시간을 오름차순으로 유지하기 위해 PriorityQueue 사용
• 작업의 요청 시점을 기준으로 정렬

1. 현재 시간 이전에 요청된 작업은 모두 큐에 추가
2. 큐에 작업이 없다면 시간을 다음 작업의 요청 시간으로 갱신
3. 큐에 작업이 있다면 작업 소요 시간이 가장 빠른 작업 수행
   1. 시간 : 작업의 소요 시간 + 대기 시간
4. 모든 작업을 완료 할 때 까지 반복

---

코드 구현

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;

        // 작업 배열을 요청 시간 기준으로 오름차순 정렬
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);

        // 우선순위 큐를 사용해 작업의 소요 시간 기준으로 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        int index = 0; // jobs 배열에서 처리할 작업의 인덱스
        int count = 0; // 완료된 작업의 수
        int total = 0; // 각 작업의 요청부터 종료까지 걸린 시간의 합
        int end = 0;   // 현재 시간

        // 모든 작업이 완료될 때까지 반복
        while(count < jobs.length) {
            
            // 현재 시간(end) 이전에 요청된 모든 작업을 우선순위 큐에 추가
            while(index < jobs.length && jobs[index][0] <= end) {
                pq.add(jobs[index++]); // 큐에 작업 추가 후, 인덱스 증가
            }
            
            if(pq.isEmpty()) { // 처리할 작업이 없는 경우
                // 다음 작업의 요청 시간으로 현재 시간 갱신
                end = jobs[index][0];
            } else {
                // 큐에서 가장 소요 시간이 짧은 작업을 꺼냄
                int[] cur = pq.poll();
                
                // 현재 시간에서 해당 작업의 소요 시간을 더해 총 소요 시간 계산
                // end: 작업이 시작된 시점, cur[0]: 요청 시점
                total += cur[1] + end - cur[0]; // cur[1] : 작업의 소요 시간, end - cur[0] : 작업의 대기 시간
                
                // 작업이 끝난 후의 시간을 업데이트
                end += cur[1];
                
                // 완료된 작업 수 증가
                count++;
            }
        }

        // 평균 시간을 계산하여 반환 (소수점 이하 버림)
        return total / jobs.length;
    }
}