[pro] 프로그래머스 level3 42627 디스크 컨트롤러 (Java) - 힙(우선순위 큐)

[문제]

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

프로그래머스

 

[풀이]

1. 소요시간이 짧은 순서대로 처리해야 평균 대기 시간이 최소가 될 것이다.

2. 소요시간이 짧더라도 요청 시점이 터무니없이 뒤에 있다면 평균 대기 시간은 늘어날 것이다. 따라서 현재 작업이 끝나는 시점보다 앞서 들어온 요청에 대해서 수행시간이 짧은 작업을 처리한다. 이때 우선순위큐를 이용한다. 

 

[코드]

 

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        //작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 
        
        //요청 순서대로 정렬
        Arrays.sort(jobs, (o1, o2)->o1[0]-o2[0]);
        //수행시간 짧은 순서대로 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->o1[1]-o2[1]);
        
        //요청이 모두 수행될 때까지
        int count = 0;
        int idx = 0;
        int end = 0;
        while(count<jobs.length){
            while(idx<jobs.length && jobs[idx][0] <= end){
                pq.add(jobs[idx++]);
            }
            
            if(pq.isEmpty()){
                end = jobs[idx][0];
            }
            else{
                int[] curr = pq.poll();
                answer += end - curr[0] + curr[1];
                end += curr[1];
                count++;
            }
            
        }
            
        answer /= jobs.length;
        return answer;
    }
}