Java - [프로그래머스]42627 - 디스크 컨트롤러

출처

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

프로그래머스

 

문제

 

하드 디스크가 요청을 한번에 하나만 수행할 수 있다고 가정하였을 때, 요청 받은 작업이 완료되는 시간의 평균이 가장 적도록 작업 순서를 정하도록 하는 문제이다.

 

요청 받은 작업이 완료되는 시간이란, 작업 요청부터 시작되기까지 기다린 시간 + 실제 작업 시간 을 말하며 이는 곧 작업이 끝나는 시간 - 작업 요청 시간이다.

풀이

이 문제를 해결하기 위해서는 두개의 우선순위가 필요하다. 바로 작업 요청시간, 작업 시간 두가지이다.

 

예제 입력에서는 jobs가 작업 요청시간대로 정렬되어 있지만, 실제 테스트 케이스에서는 아닐 확률이 높다. 정렬되어 있다고 직접 언급된 부분이 없기 때문에, 항상 고려해주어야 할 부분이다.

 

이것을 직접 정렬해주기 보다는, 우선순위 큐를 활용하여 넣음과 동시에 정렬이 되도록 구현하였다. 이로서 첫번째, 작업 요청시간의 우선순위를 확보할 수 있었으며 이것을 기준으로 문제를 해결해 나갈 예정이다.

// 작업 요청 시점을 기준으로 하는 우선순위 큐
PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> {
    return o1[0]-o2[0];
});

for (int i = 0; i < jobs.length; i++)
    q.add(jobs[i]);

 

현재 작업중인 디스크가 없다면, 작업 요청 시점이 빠른 작업을 수행하도록 구성한다.

현재 작업 중인 디스크가 있다면, 그 디스크의 작업이 끝나기 전에 요청된 디스크를 찾아 우선순위를 매겨야 한다. 이 때, 작업 시간이 짧은 디스크를 먼저 작업하는 것이 평균값을 냈을때 유리하다.

 

이유는 위에 언급했던것 과 같이 요청 받은 작업이 완료되는 시간이란 작업 요청부터 시작되기까지 기다린 시간 + 실제 작업 시간 이며, 이 공식 중 실제 작업시간은 변하지 않기에 고려하지 않아도 되며, 작업 시간이 짧은 것 부터 수행하는 것이 대기 시간을 줄일 수 있는 방법이기 때문이다.

 

현재의 작업이 종료되는 시점을 알기 위해 time 변수를 하나 선언해주었고, 만약 현재 진행중인 작업의 종료 시점보다 앞서서 요청한 작업이 있을 경우, 작업 시간이 짧은 것 부터 수행하도록 하기 위해 우선순위대로 정렬될 큐를 하나 더 선언해 주었다.

int time = 0;
// 작업 시간을 기준으로 하는 우선순위 큐
PriorityQueue<int[]> timeq = new PriorityQueue<>((o1, o2) -> {
        return o1[1]-o2[1];
    });

// 메인 반복문
while (!q.isEmpty() || !timeq.isEmpty()) {
    while(!q.isEmpty() && q.peek()[0] <= time) {
        timeq.add(q.poll());
    }
    if (timeq.isEmpty()) {
        time = q.peek()[0];
    } else { 
        int[] tmp = timeq.poll();
        answer += time - tmp[0] + tmp[1];
        time += tmp[1];
    }

}

 

만약 현재 작업이 없다면 메인 q의 맨 앞 작업의 요청 시간으로 time을 업데이트 해준다. 

 

time보다 요청 시점이 앞선 작업을 넣어 준뒤, answer에 (이전 작업이 종료될 시점 - 현재 작업이 요청된 시점 == 대기시간) + 작업 시간을 더하여 주고, 현재 작업이 끝났음을 알리기 위해 시작 시점이였던 time에 작업 시간을 더하여 주었다.

 

전체 코드

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int time = 0;

        // 작업 요청 시점을 기준으로 하는 우선순위 큐
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> {
            return o1[0]-o2[0];
        });
        PriorityQueue<int[]> timeq = new PriorityQueue<>((o1, o2) -> {
            return o1[1]-o2[1];
        });
        
        for (int i = 0; i < jobs.length; i++)
            q.add(jobs[i]);
        
        while (!q.isEmpty() || !timeq.isEmpty()) {
            while(!q.isEmpty() && q.peek()[0] <= time) {
                timeq.add(q.poll());
            }
            if (timeq.isEmpty()) {
                time = q.peek()[0];
            } else { 
                int[] tmp = timeq.poll();
                answer += time - tmp[0] + tmp[1];
                time += tmp[1];
            }
            
        }
        
        return answer/jobs.length;
    }
}