디스크 컨트롤러 (Priority Queue)

하루히즘·2021년 6월 13일
0

프로그래머스

목록 보기
12/17

설명

프로그래머스의 디스크 컨트롤러 문제다. 이전에 풀었던 파이썬 풀이와 동일하며 우선순위 큐를 자바로 활용하는 데 집중하였다.

풀이

자바로 구현한 풀이는 다음과 같다.

import java.util.*;
import java.util.stream.*;


class Solution {
    public int solution(int[][] jobs) {
        // [요청 시간, 실행 시간] 형태로 작업 대기열을 구성하는 우선순위 큐.
        PriorityQueue<int[]> workQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            // 빠른 실행 시간부터 추출해야 하므로 배열 요소 비교 Comparator 정의.
            public int compare(int[] val1, int[] val2) {
                return val1[1]-val2[1];
            }
        });
        // 특정 요청 시간의 작업들을 저장하는 Map.
        Map<Integer, List<Integer>> works = new HashMap<>();
        // 총 소요시간.
        int takenTimes = 0;
        
        // 마지막 작업까지 수행하기 위해 가장 늦게 들어오는 작업의 요청 시간 기억.
        int farthestJobInsertedTime = -1;
        // 작업 목록을 기반으로 요청 시간을 키, 실행 시간 목록을 값으로 Map에 추가.
        for(int[] job: jobs){
            List<Integer> jobOnTime = works.getOrDefault(job[0], new LinkedList<>());
            jobOnTime.add(job[1]);
            // 가장 늦게 들어오는 작업의 요청 시간 파악.
            farthestJobInsertedTime = Integer.max(farthestJobInsertedTime, job[0]);
            works.put(job[0], jobOnTime);
        }
        
        // 현재 시각: currentTime
        // 현재 진행중인 작업의 잔여 실행 시간: currentJob
        int currentTime = 0;
        int currentJob = 0;
        // 아직 대기중인 작업이 있거나 나중에 더 들어올 작업이 있다면 대기.
        while(!workQueue.isEmpty() || currentTime <= farthestJobInsertedTime) {
            // 현재 작업 수행.
            currentJob -= 1;
            // 현재 시각의 작업 목록을 우선순위 큐에 삽입.
            // 현재 시각의 작업이 없다면 default로 빈 ArrayList를 받아서 추가.
            for(int job: works.getOrDefault(currentTime, new ArrayList<Integer>(0))) {
                workQueue.add(new int[]{currentTime, job});
            }
            
            // 현재 작업을 다 처리했다면 큐에서 다음 작업을 꺼내서 실행.
            if(currentJob < 1 && !workQueue.isEmpty()) {
                int[] nextWork = workQueue.remove();
                currentJob = nextWork[1];
                // 작업을 처리하는 데 걸린 시간은 현재 시각 + 실행 시간 - 요청 시각
                takenTimes += (currentTime + nextWork[1] - nextWork[0]);
            }
            
            currentTime++;
        }
        
        // 작업을 처리하는데 걸린 시간의 합을 나눠서 평균 계산.
        return (int) takenTimes / jobs.length;
    }
}

요구사항을 직접적으로 구현한 것 외에 특이사항은 없다.

후기

이번에도 자바의 Stream을 적극 활용하였는데 특히 마지막 평균을 구하는 과정은 이 StackOverflow의 질문을 참고할 수 있었다.

Comparator

Comparator 인터페이스는 정렬이 필요한 요소들을 담는 자료구조에서 정렬 기준으로 사용된다. 이번 풀이에서 사용한 우선순위 큐 클래스(PriorityQueue)는 생성자로 이 Comparator 인터페이스를 받을 수 있다.

현재 풀이에서는 해당 작업이 삽입된 시점과 해당 작업의 실행 시간을 배열로 유지하고 있다. 왜냐면 디스크 컨트롤러에서 이미 다른 작업을 수행하고 있다면 특정 시각에 삽입된 작업이 곧바로 실행되는 것은 아니기 때문이다.

그런데 우선순위 큐로 이 작업을 정렬하려면 결국 배열끼리 비교해서 정렬해야 하기 때문에 기본값으로는 정렬할 수 없으므로 별도의 Comparator를 구현하여 우선순위 큐에 전달해줘야 한다.

이 인터페이스는 compare 메서드를 재정의할 수 있으며 두 객체를 비교할 때 첫 번째 객체가 두 번째 객체보다 앞서야 한다면 음수, 같다면 0, 뒤에 있어야 한다면 양수를 반환하도록 정의해야 한다. 즉 첫 번째 객체에서 두 번째 객체를 빼는 것과 비슷하다.

PriorityQueue<int[]> workQueue = new PriorityQueue<>(new Comparator<int[]>() {
    @Override
    public int compare(int[] val1, int[] val2) {
        return val1[1]-val2[1];
    }
});

위의 풀이에서는 배열에 [요청 시각, 실행 시간] 순서로 담겨 있기 때문에 빨리 끝날 수 있는 작업을 먼저 실행하려면 실행 시간을 오름차순으로 정렬하려면 1 번째 인덱스로 비교해야 한다.

파이썬에서는 기본적으로 정렬 방법이 구현되어 있기 때문에 그냥 튜플로 묶어서 전달해주면 되지만 자바에서 그런 걸 바라는 건 사치인 것 같다.

이번에도 좋은 문제였다.

profile
YUKI.N > READY?

0개의 댓글