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

디스크 컨트롤러 문제 링크

운영체제 시간에 배운 SJF(Shortest Job First) 기법을 직접 구현하세요! 하는 문제이다.

해당 문제를 보고 든 정리한 내용은 다음과 같다.

1개 요청 -> (작업 번호, 요청 시각, 소요 시간) 큐에 저장

1. 소요시간 짧은
2. 요청 시각 빠른
3. 작업 번호 작은
순서대로 우선순위 큐 구현

마치는 시점과 요청 작업이 겹치는 경우
요청 작업을 대기 큐에 저장한 후 우선순위가 높은 작업을 대기 큐에서 꺼냄
-> 마치는 경우와 요청 하는 경우가 겹치는 경우 우선순위 큐에 한번 넣어주어야 함

반환 시간 = 종료 시각 - 요청 시각

(기타 내용 끄적끄적...)

일단 우선순위 큐를 사용해서 소요시간이 짧은 순서부터 작업 번호 작은 순서까지 기준을 정해놓고 큐에 넣으면 정렬을 될 것 같았다.

문제는 그 이후이다. 큐에서 꺼내서 작업 처리를 어떻게 수행하지..? 예시 그림과 같이 1번 작업이 0번 작업 중에 요청해오면 이를 어떻게 처리해야할까..?

아무리 생각해봐도 명쾌한 답안이 떠오르지 않아 다른 사람 풀이를 참고하기로 했다.

문제를 푸는 열쇠는 다음과 같았다.

1. jobs 배열을 작업 요청 시점으로 오름차순 정렬 (jobs가 순서대로 주어진다는 보장이 없음...)
2. 전체 시간 경과를 나타내는 idx와 하나의 작업이 끝난 시각을 나타내는 time 변수 (작업 종료 시간) 선언
3. 현재 시각(time)까지 들어온 작업들을 전부 큐에 집어넣기
   -> 이렇게 하면 하나의 작업이 끝날 때 마다 다음 중 하나를 수행하게 된다.
   3-1. jobs[idx][0] <= time이 true인 경우 요청온 작업을 집어넣는다.
   3-2. pq.poll() 부분을 실행하여 큐에 있던 작업을 하나 빼서 수행한다.
4. 누적한 결과를 작업 개수로 나누어서 정답 반환

가장 헷갈리는 부분이 3번 과정인데, 예시 데이터인 [[0, 3], [1, 9], [3, 5]]을 기준으로 생각해보자.

가장 처음에 [0, 3]이 작업을 수행한 이후에는 time = 3이 된다.

따라서 [1, 9], [3, 5] 모두 큐에 집어 넣을 수 있고(3-1에 의해) 소요 시간을 기준으로 정렬하므로 [3, 5]를 먼저 실행한다.

따라서 문제에 주어진 조건을 모두 만족할 수 있다.

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
        PriorityQueue<Jobs> pq = new PriorityQueue<>();
        
        int idx = 0;
        int time = jobs[0][0];
        
        while (idx < jobs.length || !pq.isEmpty()) {
            while (idx < jobs.length && jobs[idx][0] <= time) {
                pq.add(new Jobs(idx, jobs[idx][0], jobs[idx][1]));
                idx++;
            }
            
            if (pq.isEmpty()) {
                time = jobs[idx][0];
                pq.add(new Jobs(idx, jobs[idx][0], jobs[idx][1]));
                idx++;
            }
            
            Jobs job = pq.poll();
            time += job.duration;
            answer += time - job.requestTime;
        }
        
        return answer / jobs.length;
    }
}

class Jobs implements Comparable<Jobs> {
    
    int jobNumber;
    int requestTime;
    int duration;
    
    public Jobs(int jobNumber, int requestTime, int duration) {
        this.jobNumber = jobNumber;
        this.requestTime = requestTime;
        this.duration = duration;
    }
    
    @Override
    public int compareTo(Jobs o) {
        int c = Integer.compare(this.duration, o.duration);
        if (c != 0)
            return c;
        
        c = Integer.compare(this.requestTime, o.requestTime);
        if (c != 0)
            return c;
        
        return Integer.compare(this.jobNumber, o.jobNumber);
    }
}

문제에서는 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 라고 했지만, 소요시간 기준으로만 정렬해도 로직 상 문제를 해결하는 데는 큰 문제가 없는 것 같다...

그리고 문제를 보고 idx, time과 같은 변수를 선언하고, 조건 반복을 통해 로직을 설계하는 부분을 캐치해야 하는데, 이 부분이 어려운 것 같다.
(오히려 우선순위 큐를 사용해야겠다!라는 점은 쉽게 떠올릴 수 있는 것 같다.)

핵심은 시간(time)이 바뀔 때마다, time 이하로 도착한 job을 전부 pq에 넣고, pq에서 하나 꺼내서 실행한다는 것