[JAVA] 프로그래머스 디스크 컨트롤러_우선순위큐

 

문제 : 

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

프로그래머스

 

 

접근 :

 

  - 대기 우선순위 큐를 생성하여 요청을 받은 시간을 오름차순 기준으로 저장

 

  - 만약 대기 큐의 원소 중 시작시간이 현재시간 이전이면 모두 처리 우선순위 큐에 저장(소요되는 시간이 짧은 순)

 

  -  처리 큐에 작업이 있다면 처리하고 현재시간과 소요시간을 모두 갱신한다.

 

  - 만약 처리 큐에 작업이 없다면 현재 시간을 처리 큐의 첫번째 원소의 시작시간으로 갱신한다. 

 

 - 대기 우선순위 큐와 처리 우선순위 큐가 모두 빌때까지 작업을 수행한다.

 

 

 

 

 

 코드 구현 : 

 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<int[]> waitingQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> processingQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        
        for(int[] job : jobs) waitingQueue.offer(job);

        int answer = 0;
        int now = 0;

        while (!waitingQueue.isEmpty() || !processingQueue.isEmpty()) {
            // 현재 시간 이내에 요청된 모든 작업을 처리 큐로 이동
            while (!waitingQueue.isEmpty() && waitingQueue.peek()[0] <= now)
                processingQueue.offer(waitingQueue.poll());
            
            if (!processingQueue.isEmpty()) {
                int[] job = processingQueue.poll();
                now += job[1];
                answer += now - job[0];
                continue;
            }
            // 처리할 작업이 없다면 다음 요청 시간으로 이동
            now = waitingQueue.peek()[0];
        }
        return answer / jobs.length;
    }
}