[프로그래머스/java] lv3. 디스크 컨트롤러

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/42627

🌱 문제

🌱 풀이

• [작업의 요청부터 종료까지 걸린 시간의 평균]을 가장 최소로 하기 위해 어떤 기준으로 작업을 처리할지 생각하는게 가장 중요했다.

• 아래 그림은 주어진 예시가 정답이 되기 위한 순서이다.
  • 작업 A는 0초부터 3초간 처리된다.
  • 작업 C는 요청되는 시점이 2초이지만 작업 A가 끝난 후, 3초부터 시작하여 6초간 처리된다.
  • 작업 B는 요청되는 시점이 1초이지만 작업 B가 끝난 후, 9초부터 시작하여 9초간 처리된다.
• 위 예시에 (8,2) (4,9), (6,3) (7,5) 와 같은 작업4개가 추가로 더 존재한다고 생각하자.
  (우선, A,B는 제외하고 C와 추가로 쓴 4개의 작업에서만 생각)
• [작업의 요청부터 종료까지 걸린 시간의 평균]을 구하는게 목적이므로, 최대한 작업들이 기다리는 시간이 없어야 한다. 그러므로 요청시간이 빠른것을 무조건 다음 작업으로 선택하는 것이 아니라, 요청시간의 기준을 만족하면서 처리 소요시간이 가장 적은것을 다음 작업으로 선택해야한다.
• 위 그림에 나타낸 것과 같이 (8,2) (4,9), (6,3) (7,5)와 같은 작업 4개의 요청시점은 작업C가 끝나는 시점(9)보다 작기 때문에 작업 C의 처리가 끝난 후, 다음 작업으로 선택할 수 있는 후보가 된다.
• 이 작업들은 우선순위큐에 담는다. 이때 우선순위 큐는 작업의 소요시간 기준으로 오름차순으로 우선순위가 결정되는 큐이다.
• 그럼 현재 상황에서, 핑크색 글자인 (8,2) (4,9) (6,3) (7,5) 순서를 갖게되고, 가장 우선순위 높은 것을 처리한다. 처리하면서 또 작업(8,2)가 끝나기 전에 요청된 작업들을 우선순위 큐에 넣는 과정을 반복한다.
• 나머지 풀이는 주석에 자세히 작성했다.

🌱 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int n =jobs.length;
        Arrays.sort(jobs, new Comparator<int[]>(){ // 요청된 시간 기준 오름차순 정렬, 같다면 소요시간이 적은 순서대로.( 두번째 조건 안하면 테케하나 틀림)
            @Override
            public int compare(int[] arr1, int[] arr2){
                if(arr1[0]==arr2[0])
                    return arr1[1]-arr2[1];
                return arr1[0]-arr2[0];
            }
        });
        
        //작업의 소요시간 기준 오름차순 정렬
        PriorityQueue<int[]> pq =  new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] arr1, int[] arr2){
                return arr1[1]-arr2[1];
            }
        });
        
        pq.offer(jobs[0]); //제일 처음 수행되는 작업 넣기
        int index=1; // 0번째는 넣었으니까 1번째부터 인덱스 시작
        int end=jobs[0][0]; // end: 현재 시간 흐름
        int sum=0;
        
        while(!pq.isEmpty()){ // 모든 작업이 끝날때까지 반복 
            int[] cur = pq.poll(); // 현재 수행되는 작업 
            end+=cur[1]; // 시간의 흐름: 현재 수행되는 작업이 끝난시점
            sum+=end-cur[0]; // 현재 작업의 (끝난시점)-(요쳥된시점) 만큼 sum에 더해줌
            
            while(index<n && jobs[index][0]<end ){ // while문안의 조건 순서 주의. (순서 다르면 index가 jobs의 범위밖으로 나가는 순간 런타임에러)
                pq.offer(jobs[index++]); // 전에 처리되던 작업이 처리되는 동안,  요청되었기 때문에 pq에 넣어주기.
            }
            
            if(index<n && pq.isEmpty()){ // pq가 비어있다는것은 직전 작업이 끝고 나서, 다음 작업이 수행됨.
                end=jobs[index][0]; // 시간의 흐름은 그다음 작업의 시작시간으로 이동.
                pq.offer(jobs[index++]); //  다음 수행할 작업 넣어주기 
                
            }
        }
        System.out.println("sum: "+sum);
        return sum/n;
    }
}