EunSung.log

디스크 컨트롤러

2 min read

문제 정보

풀이

문제에서 다음과 같은 순으로 우선순위가 높다고 명시되었다.

  1. 작업 소요 시간이 짧은 것
  2. 작업 요청 시간이 빠른 것
  3. 작업 번호가 작은 것

즉, SJF(Shortest Job First) 스케쥴링을 구현하는 문제다.

우선 주어진 작업(jobs[][])을 요청 시점을 기준으로 정렬한다. 그 후 소요 시간 기준 최소 힙(우선순위 큐)을 구성하고, 해당 우선순위 큐를 풀이에 사용한다.

이렇게 하면 문제에서 명시한 우선순위가 높은 순으로 정렬할 수 있다.

자바의 Arrays.sort()는 객체 배열에 대해 사용될 경우 안정 정렬인 Tim sort를 사용하기 때문에, 작업 번호에 대한 우선 순위 조건도 만족할 수 있기 때문이다.

코드

import java.util.*;
 
class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (j1, j2) -> Integer.compare(j1[0], j2[0]));
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        
        int cur = 0;
        int idx = 0;
        int turnaround = 0;
        int completed = 0;
        
        while (completed < jobs.length) {
	        // 현재 시각 이전에 요청된 작업을 모두 우선순위 큐에 추가
            while (idx < jobs.length && jobs[idx][0] <= cur)
                pq.offer(jobs[idx++]);
            
            if (pq.isEmpty()) {
	            // 처리할 수 있는 작업이 없으면 다음 작업 요청 시각으로
                cur = jobs[idx][0];
                continue;
            }
            
            int[] job = pq.poll();
            cur += job[1];
            turnaround += cur - job[0];
            completed++;
        }
        
        return turnaround / jobs.length;
    }
}

백링크