[프로그래머스] 디스크 컨트롤러 (Heap)

문제 소개

오늘 풀었던 프로그래머스 - 디스크 컨트롤러 문제를 정리합니다.

이 문제는 요청 시점과 소요 시간이 주어진 여러 작업을
짧은 작업 시간 우선(SJF, Shortest Job First) 방식으로 스케줄링(소요시간 짫은 것>요청시간 빠른 것>작업번호 작은 것)하여,
전체 평균 반환 시간(turnaround time)의 정수값을 구하는 문제입니다.

문제 링크: 디스크 컨트롤러 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. jobs 배열을 요청 시점(시작 시간) 기준으로 정렬
2. 현재 시간까지 들어온 작업을 우선순위 큐에 추가
3. 우선순위 큐는 작업 소요시간 기준 오름차순 됨
4. 현재 시간이 다음 작업 요청 시점보다 이전이라면 → 다음 요청시간으로 건너뜀
5. 가장 짧은 작업부터 처리하면서 전체 반환 시간 누적

---

해결 과정 및 코드

핵심 아이디어

1. jobs[i] = [요청시각, 소요시간]
2. 처리 중에 요청된 작업을 우선순위 큐에 넣음
3. 현재 시간 기준으로 실행 가능한 작업 중, 가장 소요 시간이 짧은 것부터 수행

코드

시간 복잡도 : 최대 O(N^3) (모든 칸에 대해 DFS 탐색)

import java.util.*;

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

        // 작업이 요청되는 시점 기준으로 오름차순 정렬
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);

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

        int now = 0; // 현재 시간
        int jobIndex = 0; // 작업 배열 인덱스
        int completed = 0; // 처리 완료된 작업 개수

		// 모든 작업을 처리했다면 종료
        while (completed < jobs.length) {
        
            // 현재 시간까지 들어온 작업(이전 작업 처리 중 요청된 작업)을 모두 우선순위 큐에 추가
            while (jobIndex < jobs.length && jobs[jobIndex][0] <= now) {
                pq.add(jobs[jobIndex++]);
            }

            if(!pq.isEmpty()) { // 이전 작업 처리 중 요청된 작업이 있는 경우
                int[] job = pq.poll();
                now += job[1]; // 작업 수행 후 시간 증가
                answer += now - job[0]; // 요청 시점부터 종료까지 걸린 시간 누적
                completed++; // 처리 완료된 작업 개수 1 증가
            } else { // 이전 작업 처리 중 요청된 작업이 없는 경우
                // 처리할 작업이 없다면 다음 작업 요청 시간으로 점프
                now = jobs[jobIndex][0];
            }
        }

        return answer / jobs.length;
    }
}