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

문제

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

프로그래머스

 

문제 분석

• 디스크를 스케줄링하여 작업 시간이 제일 적도록 하는 문제이다.
• 작업 (작업이 요청되는 시점, 작업의 소요 시간) 배열을 받아 어떤 작업을 먼저 처리하면 작업의 평균 처리 속도가 제일 빠를 지 알아내야 한다.
• 문제 예시처럼 작업 길이가 짧은 작업 부터 처리해주는 것이 이 문제를 푸는 방법이다.
• 주의할 점은 작업 소요 시간이 길더라도 현재 실행 중인 작업이 없다면 먼저 실행시켜야 한다.
• 한번 실행된 작업은 끝날 때까지 실행된다.
• 작업의 개수는 1~ 500 개 이다.
• 작업의 소요 시간은 1 ~ 1000 이고, 요청되는 시점은 0 ~ 1000 이다.

 

접근 방법

이 문제는 현재 시점에서 처리할 수 있는 작업 중 가장 소요 시간이 짧은 작업을 선택해 실행 시켜주면 된다.

매번 가장 작은 값을 실행 시키기 때문에 우선순위 큐를 활용하면 문제를 쉽게 해결할 수 있다.

1. 우선 작업 배열을 요청되는 시점 기준으로 오름 차순 정렬이 필요하다. 

2. 현 시점에 실행가능 한 작업들을 우선순위 큐에 넣는다.

3. 우선 순위 큐에서 작업을 하나 빼서 처리한다. (소요 시간이 제일 작은 작업이 뽑힌다.)

4. 2, 3 과정을 모든 작업이 처리될 때까지 반복한다.

5. 평균 걸린 시간을 계산해 반환한다.

 

 

코드 구현

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int time = 0;
        int finishedJobCnt = 0;
        int totalJobTime = 0;
        Queue<int[]> pq = new PriorityQueue<>((e1, e2) -> {
            return e1[1] - e2[1];
        });

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

        int idx = 0;
        while(finishedJobCnt < jobs.length){
            while (idx < jobs.length && jobs[idx][0] <= time) {
                pq.add(jobs[idx++]);
            }

            if(!pq.isEmpty()){
                int[] cur = pq.remove();
                time += cur[1];
                totalJobTime += time - cur[0];
                finishedJobCnt++;
            }else{
                time++;
            }
        }

        return totalJobTime / finishedJobCnt;
    }
}