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

문제 보기



풀이

  • 작업을 수행할 때 대기중인 작업들 중에서 가장 짧은 시간이 소요되는 작업을 수행하기 위하여 최소힙 사용(PriorityQueue)
  • 다음에 수행될 작업의 인덱스 indexOfJobs
  • 직전 작업이 끝난 시간 endTime
  • 작업들의 요청 시간부터 완료 시간까지 합 totalTime
  • 수행 완료된 작업들의 수 numberOfCompletedJobs

  • endTime전에 요청 시간이 시작되는 작업들을 최소힙에 넣음
  • 최소힙이 비어있는 경우 다음에 수행될 작업의 요청 시간이 endTime보다 큰 경우 이므로 endTime을 다음에 수행될 작업의 요청시간으로 변경
  • 나머지 경우 작업 수행 -> totalTime에 요청 시간부터 끝난 시간까지 계산하여 더해주고 endTime을 수행 완료 시간으로 변경 후 numberOfCompletedJobs 증가 시킴
class Solution {
    public int solution(int[][] jobs) {
        int indexOfJobs = 0;
        int endTime = 0;
        int totalTime = 0;
        int numberOfCompletedJobs = 0;

        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        while (numberOfCompletedJobs < jobs.length) {
            while (indexOfJobs < jobs.length && jobs[indexOfJobs][0] <= endTime) {
                pq.add(jobs[indexOfJobs++]);
            }

            if (pq.isEmpty()) {
                endTime = jobs[indexOfJobs][0];
            } else {
                int[] job = pq.poll();
                totalTime += endTime + job[1] - job[0];
                endTime += job[1];
                numberOfCompletedJobs++;
            }
        }

        return totalTime / jobs.length;
    }
}

좋은 웹페이지 즐겨찾기