[프로그래머스] 디스크 컨트롤러 Java 풀이 및 해설

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

프로그래머스

풀이 방법

1. 수행할 작업 목록을 요청 시각 오름차순으로 정렬한다.
2. 우선순위 큐 선언한다. 소요 시간이 작은것이 먼저 뽑아져 나온다.
   1. X, Y 두개의 작업을 수행할 수 있을때 X 작업을 끝내는데 a 시간이 걸리고 Y 작업을 끝내는데 b 시간이 걸린다고하자
   2. 두개의 작업 앞에 c 시간이 걸린다면
   3. X -> Y 순으로 작업을 한다면 각 작업을 끝내는데 걸리는 시간은
   4. X : c + a, Y : c + c + a + b 이다.
   5. 만약 X가 오래 걸리는 작업이고 Y는 짧은 작업이라면 Y는 X 때문에 작업을 끝내는데 걸리는 시간이 늘어난다.
   6. 즉, 짧게 걸리는 작업을 우선으로 작업하는것이 각 작업을 끝내는데 걸리는 시간이 최소가 된다.
3. 정렬된 작업 목록에서 작업 하나를 뽑아온다.
4. 이 작업을 끝내는동안 들어올 수 있는 작업들을 우선순위 큐에 넣는다.
5. 우선순위 큐에서 작업을 뽑아 온다.
6. 이 작업을 끝내는동안 들어 올 수 있는 작업들을 우선순위 큐에 넣는다.
7. 우선순위 큐가 빌때까지 5 -> 6 과정을 반복한다.

 

전체 코드

import java.util.*;
class Solution {
    
    class Job {
        int requestTime; // 요청 시각
        int needTime; // 소요 시간
        
        public Job(int requestTime, int needTime) {
            this.requestTime = requestTime;
            this.needTime = needTime;
        }
    }
    
    public int solution(int[][] jobs) {
        int answer = 0; // 각 작업이 요청부터 종료까지 걸린 시간 (아직 평균은 안냈음)
        
        // 요청 오름차순
        Arrays.sort(jobs, (o1, o2) -> {
            if(o1[0] == o2[0])
                return o1[1] - o2[1];
            return o1[0] - o2[0];
        });
        
        // 우선순위 큐 : 소요시간이 작은게 먼저 나옴. 수행해야할 작업 목록
        PriorityQueue<Job> pq = new PriorityQueue<>((o1, o2) -> {
            return o1.needTime - o2.needTime;
        });
        
        // 수행할 작업
        int idx = 0;
        while(idx < jobs.length) {
            
            pq.add(new Job(jobs[idx][0], jobs[idx][1])); // 첫번째 작업 수행
            int curTime = jobs[idx][0]; // 현재 시각
            
            // 첫번째 작업을 수행하며 들어온 작업들 확인
            idx++;
            while(pq.size() != 0) {
                Job job = pq.poll();
                answer += (job.needTime + curTime) - job.requestTime; // 작업 처리 시간
                curTime += job.needTime; // 현재 시간은 작업 소요 시간을 더해줌

                // 현재 시간 이내 다른 작업이 들어올 수 있는지 확인
                while(idx < jobs.length && jobs[idx][0] <= curTime) {
                    pq.add(new Job(jobs[idx][0], jobs[idx][1]));
                    idx++;
                }
            }
        }
        
        answer /= jobs.length;
        return answer;
    }
}