[lv.3] 디스크 컨트롤러

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

• 문제
  각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

  jobs의 길이는 1 이상 500 이하입니다.
  jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
  각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
  각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
  하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

• 풀이
  1) jobs를 요청시간 순으로 정렬 Arrays.sort(jobs, (o1, o2)->o1[0]-o2[0]);
  2) 우선순위 큐를 수행시간 순으로 정렬 PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)->o1[1]-o2[1]);
  3) 작업이 끝나는 시점까지 들어온 요청을 queue에 넣음
  4) 만일 queue가 비어있으면 그 다음 요청을 수행시킴 (end를 변경)
  5) 수행되는 동안 answer에 수행시간+끝난시점-대기시간을 더함, 이후 끝난 시점에 수행시간 더함

• 소감
  정말 어려웠던 문제. 결국 자력으로 풀지 못했다.
  하지만 기분이 나쁘지는 않았는데 우선 문제의 퀄리티도 좋았고, 큐를 쓸 때 사용하던 코드의 틀을 깨부순 문제이기에 학습이 잘 되었다.
  이런 문제들을 더 많이 만나서 나의 실력도 같이 올려보자.

• 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int cnt = 0; // 수행된 요청 수
        int end = 0; // 작업이 끝난 시점
        int idx = 0; // 인덱스
        int answer = 0;
        Arrays.sort(jobs, (o1, o2)->o1[0]-o2[0]);
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)->o1[1]-o2[1]);
        while(cnt<jobs.length){
            while(idx<jobs.length && end>=jobs[idx][0]){
                queue.add(jobs[idx++]);
            }
            if(queue.isEmpty()){
                end = jobs[idx][0];
            }
            else{
                int[] now = queue.poll();
                answer += now[1]+end-now[0];
                end += now[1];
                cnt++;
            }
            
        }
        return (int)answer/jobs.length;
    }
}