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

코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

주어진 작업들 중 소요시간이 짧은 작업을 먼저 수행하는 그리디 알고리즘으로 문제를 해결할 수 있을 것이라고 생각하였습니다.

작업의 수행은 LIFO의 자료구조인 Queue를 사용하고자 하였고, 작업 수행시간에 따른 정렬을 수행할 수 있는 PriorityQueue를 이용하는 것이 좋다는 생각을 하였습니다.

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer=0, index=0, time=0, count=0;
        Arrays.sort(jobs,(a,b) -> a[0]-b[0]);
        PriorityQueue<int[]> process = new PriorityQueue<>(512,(x,y) ->x[1]-y[1]);
        time = jobs[0][0];
        while(count<jobs.length){
            while(index<jobs.length&&time>=jobs[index][0]){
                process.offer(jobs[index++]);
            }
            if(!process.isEmpty()){
                int[] current = process.poll();
                time+=current[1];
                answer+=time-current[0];
                count++;
            }else{
                time = jobs[index][0];
            }
        }
        return answer/jobs.length;
    }
}

테스트를 통과하는 코드를 작성하였습니다.

PriorityQueue는 생성자에 Comparator를 매개변수로 받아 원소의 순서 비교를 할 수 있습니다.

모든 작업들을 요청시간에 따라 정렬한 후, 받을 수 있는 작업들을 모두 큐에 삽입, 소요시간 순서에 따라 작업을 수행함으로서 요청 - 완료까지 걸리는 평균 시간의 최소 값을 얻을 수 있습니다.