힙(우선순위 큐)의 활용 - 프로그래머스 디스크 컨트롤러

문제

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

프로그래머스

 

 

문제 접근

• 우선순위 큐 유형의 문제인데 우선순위가 명확히 제시되어 있지 않고, 문제를 확인함으로서 직접 우선순위를 찾아야 하는 문제이다.
• 해당 우선순위 큐에서 선정해야할 우선순위는 현재 시간에 들어온 작업들 중 작업에 걸리는 시간이다. 즉 현재 시간에 들어온 요청들 중 가장 짧은 작업 시간을 가지는 데이터가 먼저 빠져나가게 된다.
• 대신 데이터가 요청시간 순서대로 들어오는걸 문제에서 보장하지 않기 때문에 해당 부분부터 먼저 처리해야한다. 이는 정렬을 통해 처리할 수 있다.

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        Arrays.sort(jobs, (x, y) -> x[0] - y[0]); // sorting by requesting time
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
        
        int curTime = 0;
        int idx = 0;
        int completeCnt = 0;
        
        while(completeCnt < jobs.length){
            while(idx < jobs.length && jobs[idx][0] <= curTime){
                pq.offer(jobs[idx++]);
            }
            
            if(pq.isEmpty()){
                curTime = jobs[idx][0];
            } else{
                int[] job = pq.poll();
                answer += curTime + job[1] - job[0];
                curTime += job[1];
                completeCnt++;
            }
        }
        
        return (int)Math.floor(answer / jobs.length);
    }
}

• 먼저 현재 시간 curTime 이하에 들어온 요청들은 이미 모두 도착한 것이기 때문에 우선순위 큐에 집어넣는다.
• 만약 우선순위 큐가 비었다면, 즉 하드디스크가 작업을 수행하고 있지 않다면 먼저 요청이 들어온 작업부터 처리해야 하므로 작업들이 들어있는 jobs에 있는 시간으로 현재 시간을 이동시킨다.
• 그것이 아니라면 처리종료 시간만큼 시간을 이동시키고, 다음 루프로 넘어간다.