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

힙 문제입니다.

 

한 번에 하나의 일만 처리할 수 있는 디스크에 여러 요청이 들어왔을 때, 요청 대기시간의 평균을 가장 짧게 만들어야 합니다.

입력 값과, 스케줄 길이에 따라 정렬을 하게 된다면 O(Nlog(N))으로 문제를 해결할 수 있습니다.

 

특정 시간을 기준으로 해결할 수 있는 있는 요청을 우선순위 큐에 삽입하여 하나씩 처리하면 됩니다.

 

[구현 코드]

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    private static class Job implements Comparable<Job> {
        int s, d;

        public Job(int s, int d) {
            this.s = s;
            this.d = d;
        }

        @Override
        public int compareTo(Job o) {
            return this.d - o.d;
        }
    }

    public static int solution(int[][] jobs) {
        PriorityQueue<Job> pq = new PriorityQueue<>();

        // 요청을 오름차순으로 정렬
        Arrays.sort(jobs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 테케 8, 18번
                if(o1[0] == o2[0]){
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        int n = jobs.length;
        int idx = 0;
        int end = 0;
        int cnt = 0;
        int total = 0;
        while (cnt < n) {

            // 현재 시간을 기준으로 작업할 수 있는 요청을 우선순위 큐에 할당
            if(idx<n) {
                while (jobs[idx][0] <= end) {
                    pq.add(new Job(jobs[idx][0], jobs[idx][1]));
                    idx++;
                    if (idx == n) break;
                }
            }

            // 현재 시간으로 작업할 요청이 없을 때
            if (pq.isEmpty()) {
                if(idx<n) {
                    pq.add(new Job(jobs[idx][0], jobs[idx][1]));
                    end = jobs[idx][0];
                    idx++;
                }
            }

            // 가장 우선순위가 높은 것 부터 처리
            if (!pq.isEmpty()) {
                Job job = pq.poll();
                total += (end - job.s + job.d);
                end += job.d;
                cnt++;
            }
        }

        return total / n;
    }
}