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

문제

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

프로그래머스

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
        
        PriorityQueue<Job> pq = new PriorityQueue<>();
        
        int nowTime = 0;
        int totalTime = 0;
        int jobIndex = 0;
        int jobCount = 0;
        
        while(jobCount < jobs.length) {
            while(jobIndex < jobs.length && jobs[jobIndex][0] <= nowTime) {
                pq.add(new Job(jobs[jobIndex][0], jobs[jobIndex][1]));
                jobIndex++;
            }
            
            if(pq.isEmpty()) {
                nowTime = jobs[jobIndex][0];
            }
            else {
                Job nowJob = pq.poll();
                int waitTime = (nowTime - nowJob.insertTime) + nowJob.taskTime;
                nowTime += nowJob.taskTime;
                totalTime += waitTime;
                jobCount++;
            }
        }
        
        return totalTime / jobs.length;
    }
    class Job implements Comparable<Job> {
        int insertTime;
        int taskTime;
        public Job (int insertTime, int taskTime) {
            this.insertTime = insertTime;
            this.taskTime = taskTime;
        }
        @Override
        public int compareTo(Job o) {
            return Integer.compare(this.taskTime, o.taskTime);
        }
    }
}

 

접근방법

실행시간이 짧은 순으로 pq에 정렬하고 현재 시간보다 뒤에 요청들어온 job을 만나면 nowTime을 업데이트 해준다.

 

시행착오

jobs를 정렬하지 않아서 채점결과 한개빼고 모두 틀렸다.

뭔가 이해가 잘 가지 않아서 찾아보니 이 문제의 핵심은 현재시간에서 처리가 가능한 것 중 작업시간이 짧은 순으로 처리를 하는것이라고 한다.

jobs가 시간순으로 되어있다는 보장이 없는 점에 따라서 실행시간 순 정렬이 꼭 필요한거 같다.