99클럽 코테 스터디 5일차 TIL: [프로그래머스] 디스크 컨트롤러

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

프로그래머스

• 현재 시간까지 들어온 job들을 찾는 과정에서는 job들 중에 요청 시간이 적은 순으로 빼내야 한다.
• 이어서 현재 시간까지 들어온 job들 중 소요 시간이 가장 적은 job을 찾아야 하므로 이때는 job들 중에 소요 시간이 적은 순으로 빼내야 한다.
• 따라서 요청 시간이 기준인 우선순위 큐와 소요 시간이 기준은 우선순위 큐로 총 2개의 큐를 사용하면 된다.
• 주의할 점으로는, 큐를 사용할 때 항상 큐가 비어있는지를 확인하자! 예를 들어 다음 코드에서도 현재 시간까지 들어온 요청이 없다면? 무작정 ready 큐에서 poll()하면 안된다. 현재 시간까지 들어온 요청이 없으므로 다음 요청까지 시간을 흘려 보내야 한다.

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        
        PriorityQueue<Job> que = new PriorityQueue<>((o1, o2) -> o1.start - o2.start);
        PriorityQueue<Job> ready = new PriorityQueue<>((o1, o2) -> o1.duration - o2.duration);
        
        for (int[] job : jobs) {
            que.add(new Job(job[0], job[1]));
        }
        
        int cur = 0;
        int sum = 0;
        
        while (!(que.isEmpty() && ready.isEmpty())) {
            // 현재 시간까지 들어온 요청들 ready에 담기
            while (!que.isEmpty() && que.peek().start <= cur) {
                ready.add(que.poll());
            }
            
            // 현재 시간까지 들어온 요청들 중 소요 시간이 적은 걸 처리하기
            if (ready.isEmpty()) {
                cur = que.peek().start;
            } else {
                 Job job = ready.poll();
                cur += job.duration;
                sum += cur - job.start;
            }
           
        }
        
        return sum / jobs.length;
    }
    
    public class Job {
        
        int start;
        int duration;
        
        public Job(int start, int duration) {
            this.start = start;
            this.duration = duration;
        }
    }
}