[Programmers / Level 3] 42627. 디스크 컨트롤러 (Java)

💡 Info

• 난이도: Lv3
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/3/디스크 컨트롤러

입출력 조건

입출력 예시

문제 이해

• 주어진 작업들이 주어졌을 때 평균 대기 시간을 최소화하는 방식으로 처리하면 되는 문제

알고리즘

풀이 시간 : 1시간 25분

• 도착 시간을 기준 작업 정렬
• 우선 순위 큐로 작업을 소요 시간 순으로 처리
• 현재 시간 : 도착한 작업은 큐에 넣고, 큐에서 가장 소요 시간이 짧은 작업을 꺼냄
• 대기 시간 : 각 작업 대기 시간 구해서 합평균으로 대기 시간 반환

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

        int time = 0;
        int total = 0;
        int count = 0;
        int index = 0;

        while (count < jobs.length) {
            while (index < jobs.length && jobs[index][0] <= time) {
                pq.offer(jobs[index++]);
            }

            if (pq.isEmpty()) {
                time = jobs[index][0];
            } else {
                int[] current = pq.poll();
                time += current[1];
                total += time - current[0];
                count++;
            }
        }
        int answer = total / jobs.length;
        
        return answer;
    }
}

결과