[프로그래머스_JAVA_알고리즘] 디스크 컨트롤러 #힙 #우선순위 큐

PriorityQueue를 오름차순 정렬 후, 작업 시간이 짧은 순서대로 저장하는 로직을 구현합니다.

 

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int endTime = 0;        
        
        // 오름차순 정렬
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
                PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        
        // 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높음
        int i = 0;
        while(i < jobs.length || !priorityQueue.isEmpty()){
            while(i < jobs.length && jobs[i][0] <= endTime){
                priorityQueue.add(jobs[i++]);
            }
            if(priorityQueue.isEmpty()){
                endTime = jobs[i][0];
            }
            else{
                int[] job = priorityQueue.poll();
                answer += endTime + job[1] - job[0];
                endTime += job[1];
            }
        }
        
        return answer / jobs.length;
    }
}

각 작업은 [요청시간, 작업 소요시간] 형태로 저장됩니다.

int[][] jobs = {{0, 3}, {1, 9}, {2, 6}}

 

변수는 다음과 같습니다.

int answer = 0;    // 모든 작업의 처리 시간 합계
int endTime = 0;   // 현재 작업이 끝나는 시간
int i = 0;         // 작업 배열을 순회하는 인덱스

 

 

먼저, 작업을 요청 시간 순( 0초, 1초, 2초 ...)으로 

Arrays.sort를 이용한 오름차순 정렬을 진행합니다.

Arrays.sort(jobs, (a, b) -> a[0] - b[0]);

 

그 다음, 소요시간이 짧은 순서대로 배열에 저장합니다.

PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);

람다식을 이용하면 간편하게 나타낼 수 있습니다.

 

작업이 끝난 현재 시점 endTime에서 처리할 수 있는 작업을 우선순위 큐에 추가합니다.

while(i < jobs.length || !priorityQueue.isEmpty()) {
    // 현재 시점에서 가능한 작업 찾기
    while(i < jobs.length && jobs[i][0] <= endTime) {
        priorityQueue.add(jobs[i++]);
    }
    if(priorityQueue.isEmpty()) {
        endTime = jobs[i][0];
    } else {
        int[] job = priorityQueue.poll();
        answer += endTime + job[1] - job[0];
        endTime += job[1];
    }
}

 

예를 들어, 작업 {0, 3}을 처리할 때는 다음과 같습니다.

endTime: 작업이 끝난 현재 시점(0초)

job[0]: 작업 요청시간(0초)

job[1]: 작업 소요시간(3초)

answer += endTime + job[1] - job[0]; = 3

 

다음 두 번째 작업 {1, 9}을 처리할 때는 다음과 같습니다.

endTime: 작업이 끝난 현재 시점(3초)

job[0]: 작업 요청시간(1초)

job[1]: 작업 소요시간(9초)

answer += endTime + job[1] - job[0]; = 11

 

총 처리시간 answer를 구하고 jobs.length로 나누어 모든 요청작업의 반환 시간 평균을 구할 수 있습니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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

프로그래머스