[프로그래머스] 디스크 컨트롤러 (Java, Heap, lv3)

 

---

문제 출처 

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

프로그래머스

 

문제 풀이

습관처럼 우선 순위 큐에 다 넣고, 정렬을 했었는데 경쟁을 할 때 다음 노드들의 값을 갱신 어떻게 해야 할지에서 막혀서 

많은 시간 낭비를 하였다 (습관과 사고를 고쳐야 하는데 .. )

 

예제 입력 
jobs : [[0, 3], [1, 9], [2, 6]]
result : 9

 

단순히 작업 시간 순으로 정렬한다고 해서 결과값을 구할 수 없었다

10ms(= (3 + 11 + 16) / 3)

 

 

9ms(= (3 + 7 + 17) / 3)

① 시작 시간 기준으로 jobs 오름차순 정렬하고,  우선 순위 큐에서는 작업 시간 기준 오름차순 정렬하도록 설정

② 시작 시간 <= 현재 시간 이하 인 경우 job을 우선 순위 큐에 추가

③ 작업 시간이 최소인 job 꺼내 누적 시간(총 작업 시간 - job 시작 시간(0))과 총 작업 시간(job 작업시간[1]) 구함

 

전체 코드 

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        
        Queue<int[]> que = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        
        int acc = 0; 
        int idx = 0;
        int time = 0;
        while(idx < jobs.length || !que.isEmpty()) {
            // 현재 시간 이하에서 요청한 job을 큐에 추가
            while(idx < jobs.length && jobs[idx][0] <= time) {
                que.add(jobs[idx++]);
            }
            
            if(que.isEmpty()) {
                time = jobs[idx][0]; // 작업 요청이 가장 빠른 작업을 추가한다
            } else {
                // 작업 소요시간이 가장 빠른 작업 수행
                int[] job = que.poll();
                time += job[1]; // 총 작업시간
                acc += time - job[0]; // 현재 job의 실제 작업 시간 누적
            }
            
        } 
        
        
        return (int) acc / jobs.length;
    }
}