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

[문제 설명]




출처:https://school.programmers.co.kr/learn/courses/30/lessons/42627

[문제 이해]
문제를 읽고 cpu 스케줄러 알고리즘 '최단작업시간 알고리즘 Shortest job First'이 생각이 났다.

말그대로 가장 짧은 요청시간부터 처리하면 된다고 이해했다.
그리고 문제예시에서 보다시피 작업이 겹치면 안된다.

1. 처음 풀이
   처음에 생각했던 내용은 jobs배열에서 [1]값 요청처리시간을 짧은 순으로 정렬하여
   우선순위 담아 처리하면 된다고 생각을 했다.
   예시처럼 [0,3][1,9] ,[2,6] 을 정렬하게 되면
   [0,3][2,6] [1,9] 로 정렬이 된다. 예시문제에 적용할수는 있으나 테스트케이스에서 실패가 나왔다.
   

실패의 원인은 요청되는 시점에 대해 고려하지 않아서 였다.

정답코드에 대한 설명은
1.먼저 요청되는 처리 시점으로 정렬후, 우선순위 큐안에 요청되는 시간이 짧은 순으로 처리해야한다.

2.반복문을 통해 모든 작업처리를 끝내면 종료한다.
2-1. 먼저 endpoint 변수안에 초기값 0이 설정되어 있다.
우선순위 큐안에 endpoint보다 작은 값들의 작업목록을 전부 담는다.
2-2. 큐가 비어있는 경우

2-3. 큐가 비어있지 않은 경우
원소하나를 꺼낸다.
answer += 원소.요청처리시간 + endpoint - 원소.처리 시점
현재 endpoint += 요청처리 시점을 더한다.
작업 처리 ++
3. 결과 소수점을 버린다.
return (int) Math.floor(answer/jobs.length) ;

[전체 코드]

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int count = 0; // 처리해야할 프로세스
        int endpoint = 0;
        int index = 0; // jobs의 인덱스 번호
        
        // 요청되는 시점에 대한 정렬
        Arrays.sort(jobs,(a,b)-> (a[0] - b[0]));
        // 우선순위 큐를 생성 (작업의 소요시간이 짧은 순)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        // 로직 구현
        // 모든 프로세스를 처리하면 종료
        while(count < jobs.length){
            
            while(index < jobs.length && jobs[index][0] <= endpoint){
                // 요구되는 시점이 endpoint보다 작은 경우들을 모두 큐에 담는다.
                pq.add(jobs[index]);
                index++;
            }
            
            if(pq.isEmpty()){
                endpoint = jobs[index][0];
            }else{
            int [] curr = pq.poll();
            answer += curr[1] + endpoint - curr[0]; 
            endpoint += curr[1]; 
            count++; // 프로세스 처리   
            }   
        } 
        return (int) Math.floor(answer/jobs.length);
    }
}