[프로그래머스/자바] 디스크 컨트롤러 풀이

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

프로그래머스

 

프로그래머스 코딩테스트 고득점 Kit의 힙 Level 3 문제다.

 

 

작업의 요청~종료 시간의 평균이 최소가 되어야 하므로

요청한 작업 중, 소요시간이 더 적게 걸리는 순서대로 정렬해야 한다.

즉 요청한 작업을 큐에 넣고 소요시간 별로 정렬하기 위해 우선순위 큐를 사용했다.

 

먼저 요청시점이 빠른 순서대로 우선순위 큐에 넣어야 하므로 jobs의 요청시점을 오름차순으로 정렬한다.

그리고 우선순위 큐에 들어가는 소요시간을 오름차순으로 정렬한다.

 

 

현재 sec일 때 큐에 들어갈 수 있는(sec보다 요청시점이 같거나 작은) 모든 원소를 큐에 추가한다.

큐가 비어있을 때는 큐에 넣어야할 차례의 배열 원소의 요청시점에 sec를 맞춘다.

그리고 큐가 비어있지 않을 때에는 큐에서 하나씩 빼내며 요청을 처리한다.

 

이때 temp[1]이 소요시간, sec - temp[0]이 대기한 시간이므로

 temp[1] + sec - temp[0]이 작업의 요청부터 종료까지 걸린 시간이다.

작업 별로 모두 더해주고 작업의 갯수만큼 나눠준 값이 작업의 요청부터 종료까지 걸린 시간의 평균이다.

 

간단한 문제였는데 더 복잡하게 생각하느라 시간이 걸렸던 문제다.

시간별로 처리하는 방법을 익혀야겠다.

 

import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    public int solution(int[][] jobs) {
        int sum = 0;
        
        Arrays.sort(jobs, (o1, o2) -> (o1[0] - o2[0]));

        // 요청시점, 소요시간
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));

        int sec = 0; // 시간
        int idx = 0; // 배열 인덱스
        int cnt = 0; // 요청 수행 갯수

        while(cnt < jobs.length) {
            while(idx < jobs.length && jobs[idx][0] <= sec)
                q.add(jobs[idx++]);

            if(q.isEmpty()) {
                sec = jobs[idx][0];
            }
            else {
                int[] temp = q.poll();
                sum += temp[1] + sec - temp[0];
                sec += temp[1];
                cnt++;
            }
        }
    
        return sum / jobs.length;
    }
}