프로그래머스: 디스크 컨트롤러 (Java)

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

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

 

 

 

 

 

 

 

 

---

 

풀이

(요청 시간, 소요 시간)을 갖는 class Job을 만듭니다.

우선순위 큐 2개(pq1, pq2)를 선언하는데, pq1은 요청 시간이 작은 순, pq2는 소요 시간이 작은 순으로 배열하도록 합니다. pq1은 현재 시간 t보다 요청 시간이 큰(==현재 할 수 없는) 일, pq2는 현재 시간보다 요청 시간이 작거나 같은(==현재 할 수 있는) 일을 담습니다.

jobs의 모든 원소를 Job의 형태로 pq1에 넣어줍니다.

현재 시간 t=0부터 시작하여

1) 현재 할 수 있는 일이 없다(즉, 가장 앞서 할 수 있는 일의 요청 시간이 t보다 큰 경우)면 t를 가장 먼저 할 수 있는 일의 요청 시간까지 흘려보내줍니다.

2) 현재 할 수 있는 일이 pq1에 담겨있다면 이를 pq2로 옮겨줍니다. 이후, pq2에서 가장 작은 소요 시간을 갖는 원소를 뽑아내어 t를 소요 시간만큼 늘려줍니다.

 

2) 과정이 수행될 때마다 대기 시간을 정답에 더해주고, 마지막에 나눠주면 됩니다.

 

배운 점

은근히 조건이 까다로워서 실수했습니다. 실수는 실력이니 실력을 늘려야겠습니다.

 

코드

import java.util.*;
 
class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<Job> pq1 = new PriorityQueue<>((o1, o2)-> {
            return o1.start - o2.start;
        });
        PriorityQueue<Job> pq2 = new PriorityQueue<>((o1, o2)-> {
            return o1.len - o2.len;
        });
        for (int i = 0; i < jobs.length; i++) {
            pq1.offer(new Job(jobs[i][0], jobs[i][1]));
        }
        
        int ans = 0;
        int t = 0;
        while (!pq1.isEmpty() || !pq2.isEmpty()) {
            // 일이 남아있지만, 현재 시각 t일 때 할 수 있는 일이 없는 경우
            if (pq2.isEmpty() && pq1.peek().start > t) {
                t = pq1.peek().start;
            }
            // 현재 시각보다 요청 시각이 빠르거나 같은 일은 할 수 있다.
            while (!pq1.isEmpty() && pq1.peek().start <= t) {
                pq2.offer(pq1.poll());
            }
            // 할 수 있는 일 중 가장 소요 시간이 짧은 일을 한다.
            Job temp = pq2.poll();
            t += temp.len;
            ans += (t - temp.start);
        }
        ans /= jobs.length;
        return ans;
    }
}
 
class Job {
    int start;
    int len;
    
    public Job(int start, int len) {
        this.len = len;
        this.start = start;
    }
}