[프로그래머스] 디스크 컨트롤러

※ 해당 문제의 링크는 여기입니다. ※

3단계 문제인 만큼 굉장히 어려웠던 문제였습니다.

 

이번 글에는 제한 사항 대신 알고리즘 및 전체 코드만 포스팅하겠습니다.

(제한 사항, 문제에 잘 적혀있는 데 또 적는 거 귀찮....)

 

알고리즘

가장 시간이 짧은 순서대로 일을 처리해야하는 것이 주 목적입니다.하지만 일은 한 번에 하나씩만 처리가 가능하므로일이 끝나고 나서 현재 시간때 이전에 들어온 일들 중 가장 시간이 짧은 것을 다음으로 일을 하며,하나 하나씩 처리해야하는 알고리즘을 가지고 있습니다.

단, 요청 시간. 즉, 언제 들어왔는 지 역시 파악해야하는 문제입니다.

 

전체 소스코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int end = 0;        // 수행되고난 직후의 시간
        int jobsIdx = 0;    // jobs 배열의 인덱스
        int count = 0;      // 수행된 요청 갯수

        // 원본 배열 오름차순 정렬 (요청시간 오름차순)
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);

        // 처리 시간 오름차순으로 정렬되는 우선순위 큐(Heap)
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        // 요청이 모두 수행될 때까지 반복
        while (count < jobs.length) {

            // 하나의 작업이 완료되는 시점(end)까지 들어온 모든 요청을 큐에 넣음
            while (jobsIdx < jobs.length && jobs[jobsIdx][0] <= end) {
                pq.add(jobs[jobsIdx++]);
            }

            // 큐가 비어있다면 작업 완료(end) 이후에 다시 요청이 들어온다는 의미
            // (end 를 요청의 가장 처음으로 맞춰줌)
            if (pq.isEmpty()) {
                end = jobs[jobsIdx][0];     // 작업이 끝나기 전(end 이전) 들어온 요청 중 가장 수행시간이 짧은 요청부터 수행
            }
            else {
                int[] temp = pq.poll();
                answer += temp[1] + end - temp[0];
                end += temp[1];
                count++;
            }
        }

        return answer / jobs.length;
    }
}

여담

Inner Class, 단순 계산 등 여러 방면으로 디버깅하여 최대한 효율적으로 하려고 하였으나,

잘 되지않아 결국 이중while문을 사용하게 되었습니다.

 

 

이상입니다.