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

문제

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

코딩테스트 연습 - 디스크 컨트롤러

 

접근법

우선 요청이 들어온 순서대로 정렬을 해준다. ( 그냥 단순히 작업이 짧은 순으로 정렬하면 아직 요청이 들어오지 않았는데도 실행할 수도 있기 때문에 )

요청 시간 순으로 정렬이 된 상태에서 작업 시간이 짧은 순으로 우선순위 큐에 넣는다.

우선순위 큐에는 힙에 삽입이 되는 것처럼 데이터가 들어간다.

index를 이용하여 작업을 꺼내고 time을 통해 시간을 계산한다.

자세한 내용은 코드에 주석으로 달아놓았다.

 

 

코드

import java.util.*;

public class Solution {
    public int solution(int[][] jobs) {
    
        //요청이 들어온 순서대로 정렬
        Arrays.sort(jobs, (o1, o2) -> {
            if(o1[0] <= o2[0]){
                return -1;
            }
            return 1;
        });

        //우선순위 큐에 삽입이 될 때 작업 시간 순으로 삽입이 되도록 설정
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1[1] < o2[1]) {
                return -1;
            }
            return 1;
        });

        int time = 0, index = 0, answer = 0;

        while(true){
            //아직 jobs을 다 돌지 않았고, 현재 job의 요청 시간이 현재 시간보다 이전이라면? ( 즉 요청이 이미 들어왔다면 ? )
            while(index < jobs.length && jobs[index][0] <= time){
                //해당 job을 우선순위 큐에 삽입하고 index 증가
                pq.offer(jobs[index]);
                index ++;
            }
            
            //만약 우선순위 큐가 비어있다면 해당 시간에 처리할 요청이 없다는 뜻 !
            if(pq.isEmpty()){
                //시간을 다음 job의 요청 시간으로 만들어준다.
                time = jobs[index][0];
                continue;
            }

            //큐에 job이 있다면 꺼내서
            int[] job = pq.poll();
            //job의 작업 시간만큼 time을 늘려주고
            time += job[1];
            //job의 요청 시간과 현재 시간 사이의 시간을 answer에 더해준다.
            answer += time - job[0];

            //만약 모든 job을 사용했다면 break
            if(index == jobs.length && pq.size() == 0){
                break;
            }
        }

        return answer/jobs.length;
    }
}