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

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   [작업이 요청되는 시점, 작업의 소요시간]의 형태를 가진 작업들이 들어올 때, 걸린 시간의 평균이 최소인 경우를 구하는 문제이다. 예를 들면, A[0, 3], B[1, 9], C[2, 6]의 작업들이 있을 때, A - C - B의 순서로 작업을 처리하는 것이 평균 시간이 가장 최소이다.

   2차원 배열 형태로 작업(jobs)이 주어지며 제한 사항은 다음과 같다.

 

• 1 ≤ jobs ≤ 500
• 0 ≤ 작업이 요청되는 시점 ≤ 1,000
• 1 ≤ 소요시간 ≤ 1,000
• 진행중인 작업이 없는 경우 먼저 요청이 들어온 작업부터 처리한다.

---

접근 방식

   우선 순위 큐의 개념을 이용해 문제를 해결하였다. 해결 방식은 먼저 요청 시점을 기준으로 입력을 정렬한다. 이후 시간을 기준으로 들어올 수 있는 작업 중 소요시간이 제일 짧은 작업 처리, 시간에 작업 소요시간 추가의 과정을 반복하는 형태이다.

   먼저 정렬의 이유이다. 여기서 소개한 해결방식은 현재 시간(time)을 기준으로 요청 시점(job[?][0])을 만족하는 작업들을 찾아야 한다. 효율적으로 찾기위해선 정렬된 상태여야 한다. 하지만 문제에서 jobs의 정보가 요청 시점을 기준으로 정렬되어 들어온다고 보장하지 않았다.

 

들어온 작업의 index를 저장해두고 다음에 이어서 탐색하는 방법이 효율적이다.

 

   정렬이 끝난다면 이제 우선 순위 큐를 이용해 유효한 작업들을 소요시간이 짧은 순서로 정렬해야 한다. 들어온 순서대로 작업을 처리하게 되는 경우 소요시간이 짧은 작업들이 다수 대기하게 되며 평균 대기 시간이 늘어나버리게 된다. 따라서 {0, 3}의 처리가 끝난 경우 들어온 작업({1, 9}, {2, 6}) 중 {2, 6}을 먼저 처리해야 평균 대기 시간이 짧아진다.

 

   다음 단계를 알아보자. 현재 시간을 기준으로 들어올 수 있는 작업들을 jobs에서 뽑아 큐에 저장한다. 큐에서 작업 한 개를 뽑아 소요시간 (job[1]) + 대기시간(time - job[0])만큼을 총 걸린시간(total)에 더한다. 현재 시간(time)에 소요시간만큼을 더한다.

 

 

   위의 과정을 반복하며 총 걸린시간을 구하게 된다. 다음은 반복과정이 끝나는 시점이다. 작업이 하나씩 처리되기 때문에 jobs를 끝까지 읽었다고 해도 여전히 큐에 저장된 작업이 존재할 수 있다. 모든 작업을 완수했다는 것은 큐에 저장된 작업까지 처리가 끝난 경우를 의미한다. 따라서 종료 조건은 jobs를 끝까지 읽었으며, 큐가 빈 경우여야 한다.

   반복 과정이 끝나면 '총 걸리시간 / 총 작업 수'를 반환하면 된다.

 

 

  ※ 작업 간의 텀이 길어 큐는 비었지만 jobs가 남아있는 경우도 발생할 수 있다. 이 경우 현재 시간을 현재 jobs의 화살표가 위치한 job의 요청 시간으로 초기화해주면 된다.

 

---

코드

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

public class 프로그래머스42627번 {
    public int solution(int[][] jobs) {
        //들어온 시간에 따라 정렬
        Arrays.sort(jobs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        //소요시간에 따라 정렬
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int time = 0, index = 0, total = 0;

        while (true) {
            //현재 시간을 기준으로 들어올 수 있는 작업을 우선순위 큐에 저장
            while (index < jobs.length && jobs[index][0] <= time)
                q.add(jobs[index++]);
            //작업 간의 텀이 긴 경우 다음 작업이 들어오는 시간으로 현재 시간 변경
            if (q.isEmpty()) {
                time = jobs[index][0];
                continue;
            }
            //들어온 작업 중에 소요시간이 짧은 작업부터 처리
            int[] job = q.poll();
            total += job[1] + time - job[0];
            //작업의 소요시간을 현재 시간에 추가
            time += job[1];
            //모든 작업이 들어왔으며, 모든 작업을 처리한 경우 종료
            if (index >= jobs.length && q.isEmpty()) break;
        }
        return total / jobs.length;
    }
}