[Programmers] 디스크 컨트롤러 - Java

문제

프로그래머스

 

풀이

이 문제에서 주의해야할 점이 있다. 테스트 케이스가 요청 시간 순서대로 들어온다는 명시가 없다.

1. 요청 시간을 오름차순으로 정렬해야한다.

 

우선순위가 소요시간이 짧은 순, 작업 요청 시간이 빠른 순, 작업 번호가 작은 순이라고 했다.

2번째 조건은 우리가 오름차순으로 정렬했으므로, 의미가 없다. 그리고 순서대로 들어오면 작업 번호가 작은 순이라는 것이 보장된다.

2. 우선순위 큐에서 작업 소요시간을 오름차순으로 정렬만 하면 된다.

 

3. 현재 시간을 time이라고 지정해두고, time보다 같거나 작은 경우에 요청이 된 작업들을 우선순위 큐에 넣는다.

4. 작업이 끝난 갯수와 작업의 개수가 동일할때까지 while문을 돈다.

4-1. 큐가 비어있을 경우에는, 현재 시간을 다음 작업 요청 시각으로 이동한다.

4-2. 큐가 비어 있지 않을 경우에는, 소요 시간 합계에 현재 시간에서 작업 소요 시간을 더하고 요청 시간을 뺀 것이 반환 시간이므로, 더해주고 현재 시간에서 작업 소요 시간 만큼 더해서, 시간을 이동한다.

5. 평균의 정수 부분을 반환한다.

 

소스코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        
        //작업 끝난 갯수
        int endCnt = 0;
        
        //현재 시간
        int time = 0;
        
        //작업 인덱스
        int jobIdx = 0; 
        
        //소요 시간 합계
        int sum = 0;
        
        while (endCnt != jobs.length) {
            //time 전에 들어온 작업들을 모두 우선순위 큐에 넣는다.
            while (jobIdx < jobs.length && jobs[jobIdx][0] <= time) {
                pq.add(jobs[jobIdx++]);
            }
            
            //큐가 비어있다면,
            if (pq.isEmpty()) {
                time = jobs[jobIdx][0];
            //큐가 비어있지 않다면,
            } else {
                int[] job = pq.remove();
                
                //요청 시간 소요시간 빼기
                int reqTime = job[0];
                int spendTime = job[1];
                
                //현재 시간 + 작업 소요 시간에서 요청시간을 뺀다.
                sum += time + spendTime - reqTime;
                
                //시간에서 소요시간만큼 이동
                time += spendTime;
              
                endCnt++;
            }
        }
        
        return sum / jobs.length;
    }
}