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

1. 문제

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

코딩테스트 연습 - 디스크 컨트롤러

 

2. 설명

우선순위 큐(waiting)를 사용했다.

먼저 jobs를 요청시간로 정렬하고, 현재 시간(time)에서 진행할 수 있는 작업을 waiting에 삽입했다.

waiting은 빨리 끝나는 작업 순으로 정렬되어 있기 때문에 하나씩 꺼내서 시간을 추가해줬다.

waiting이 비어있을 경우, 현재 진행할 수 있는 작업이 없으므로 time을 1씩 증가시켜줬다.

어려웠다.

 

3. 코드

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int cnt = 0;
        int time = 0;
        Queue<Job> jobList = new LinkedList<>();
        PriorityQueue<Job> waiting = new PriorityQueue<>(new Comparator<Job>() {
            @Override
            public int compare(Job j1, Job j2) { // 종료시간으로 정렬
                return j1.finish-j2.finish;
            }
        });
        
        Arrays.sort(jobs, (n1, n2)-> { // 요청시간으로 정렬
            return n1[0]-n2[0];
        });
        
        for(int[] j : jobs) {
            jobList.add(new Job(j[0],j[1]));
        }
        
        while(cnt<jobs.length) {
            while(!jobList.isEmpty() && time>=jobList.peek().start) {
                waiting.add(jobList.poll()); // 대기 중인 작업
            }
            
            if(!waiting.isEmpty()) {
                Job job = waiting.poll();
                int waitTime = time - job.start;
                time += job.finish;
                answer += (waitTime + job.finish);
                cnt++;
            } else { // 진행할 수 있는 작업이 없을 때
                time++;
            }
        }
        
        return answer/jobs.length;
    }
    static class Job {
        public int start;
        public int finish;
        private Job(int start, int finish) {
            this.start = start;
            this.finish = finish;
        }
    }
}