[프로그래머스] 디스크 컨트롤러(Lv3) - 힙(Heap)

문제

• 입력값
  • 각 작업의 요청 [시점, 소요시간]이 담겨 있는 jobs[][] 배열

---

• josb[][]에 있는 작업들을 평균 작업 속도가 최소가 되는 작업 순서대로 진행하고 평균 작업 속도를 return하라

예시

아래와 같이 A, B, C 작업이 josb[][] 배열에 있다고 가정하자.
[[0, 3], [1, 9], [2, 6]]

작업을 순서대로 처리한다면 아래처럼 처리될 것이고 평균 작업 속도는 10ms가 된다.

평균 작업 속도를 낮추기 위해 아래와 같이 작업한다면 평균 작업 속도는 0ms가 된다.

이처럼 평균 작업 속도를 가장 줄이는 방법으로 처리하면 평균 작업 속도가 얼마가 되는지 return하라

풀이

코드

1. 시작 시간 순으로jobs[][]를 정렬한다.
2. 우선순위 큐에 작업들을 소요 시간이 적은 순으로 삽입한다.
3. 모든 작업을 수행할 때까지 아래 작업을 반복한다.
   1. 작업이 끝난 현재 위치보다 작거나 같은 위치에서 요청이 들어온 작업이 있다면 우선순위 큐에 삽입한다.
   2. 우선순위 큐에 작업이 존재한다면 우선순위가 가장 높은 한 작업을 수행한 뒤 현재 위치와 총 소요 시간을 계산한다.
   3. 우선순위 큐에 작업이 존재하지 않는다면 현재 위치를 요청 시간이 가장 가까운 작업의 요청 시간으로 설정한 뒤 3-1번으로 돌아간다.

/**
jobs[][]: [[시작점1, 지속시간1], [시작점2, 지속시간2]]
*/

/** 공식
- 종료 시점: 이전 요청 종료 시점 + 지속시간
- 소요 시간: 종료 시점 - 요청 시점
*/
import java.util.*;
class Solution {
    public int solution(int[][] jobs) {

        // 소요 시간이 적은 순으로 jobs[][] 오름차순 정렬
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        // 시작 시간 순으로 jobs[][] 정렬
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);

        int close = 0; // 작업 완료 후 종료 시점
        int times = 0; // 총 소요 시간
        int idx = 0; // 대기중인 작업 개수
        int jobCount = 0; // 수행된 작업 횟수

        while (jobCount < jobs.length) {
            // 현재 실행중인 작업이 끝나는 시간 >= 새로운 작업이 시작하는 시간

            // for (int i = 0; i < jobs.length; i++) {
            //     if (now >= jobs[i][0])
            //         minHeap.add(jobs[i++]);
            // }
            while (idx < jobs.length && close >= jobs[idx][0])
                minHeap.add(jobs[idx++]);

            // 힙에 작업이 존재하면
            if (!minHeap.isEmpty()) {
                int[] job = minHeap.poll();
                close += job[1]; // 3, 3+9, 3+6+6
                times += close - job[0]; // 3-0, 3-0+9-1, 3-0+9-1+6-2
                jobCount++;
            }

            // close값 보다 멀리 작업이 있다면
            else {
                close = jobs[idx][0];
            }
        }
        return times/jobs.length;
    }
}