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

문제출처 : 링크텍스트

---

문제 설명

• 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다...
• 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

---

풀이방법

우선순위큐를 그리디하게 활용하는 결합한 복합 알고리즘 문제입니다. 먼저 입력 데이터를 쉽게 다루기 위해 jobs 배열내용을 연결리스트에 옮겨 담습니다. 그리고 매 순간마다 최적해를 빠르게 계산하기 위하여 우선순위큐를 활용하여 풀이하였습니다. 마지막으로 메서드분리를 통해 풀이의 흐름이 잘 보이도록 수정하였습니다. 풀이 중 다음 규칙에 유의하여야 합니다.

• 디스크가 일하는 도중에 요청되어 대기하고 있는 작업에 대해서는 작업시간이 짧은 요청을 우선 처리한다.
• 디스크가 일하지 않는 동안 요청된 작업은 요청시간이 이른 요청을 우선 처리한다.
  - 이 때, 배열 jobs내에서의 작업 순서는 요청시간과는 연관이 없음에 주의한다.
• 따라서, 각 작업의 우선순위는 매번 재계산되어야 한다.

마지막 answer를 리턴하는 과정에서 평균을 내는 것이 아니라 무작정 3으로만 나누고 있었던 것을 늦게 발견하여 시간을 많이 버렸습니다. 풀이 중 주석을 적극적으로 활용하고 이후 불필요한 주석을 리팩터링 과정에서 제거하는 습관을 기르자...

---

문제풀이

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Solution {
    static LinkedList<int[]> request;
    static PriorityQueue<int[]> q;
    static int timeStamp;
    static int answer;
   
    public static int solution(int[][] jobs) {
        timeStamp=0; answer=0; // 스태틱 변수를 초기화
        Arrays.sort(jobs, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        }); // 정렬되지 않은 입력은 요청순서를 우선하여 정렬
        request=new LinkedList<>(Arrays.asList(jobs)); // 그리고 빼내기 쉽게 옮겨준다.
        
        q=new PriorityQueue<>(((o1, o2) -> {
            if (timeStamp >= o1[0] && timeStamp >= o2[0]) {
                return o1[1]-o2[1];
            }
            if (o1[0] == o2[0]) {
                return o1[1]-o2[1];
            }
            return o1[0]-o2[0];
        }));
        diskProcessing();
        return Math.floorDiv(answer,jobs.length);
    }

    private static void diskProcessing() {
        while(!request.isEmpty()) {
            int[] first = request.poll();
            q.add(first); // 첫 요청은 무조건 우선하여 처리하고
            timeStamp = first[0]; // 첫 시작시간 초기화
            int localAnswer = 0;  // 첫 소요시간 초기화
            localAnswer = getLocalAnswerOfRequestWhileProcessing(localAnswer);
            answer += localAnswer;
        }
    }

    private static int getLocalAnswerOfRequestWhileProcessing(int localAnswer) {
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            localAnswer += (timeStamp - curr[0]) + curr[1]; // 소요시간 추가
            timeStamp += curr[1]; // 시점 갱신
            while (!request.isEmpty() && request.peek()[0] <= timeStamp) { // 작업도중에 들어온 요청이라면 q에 추가
                q.add(request.poll());
            }
        }
        return localAnswer;
    }
}

---