프로그래머스 - 디스크 컨트롤러 (Heap) / Level 3 / Java

문제 📋

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

풀이 📝

import java.util.*;

class Task {
    private int requestTime; // 요청시간
    private int turnaroundTime; // 소요시간
    
    public Task(int requestTime, int turnaroundTime) {
        this.requestTime = requestTime;
        this.turnaroundTime = turnaroundTime;
    }
    
    public int getRequestTime() {
        return requestTime;
    }
    
    public int getTurnaroundTime() {
        return turnaroundTime;
    }
}


class Solution {
    public int solution(int[][] jobs) {
        int curTime = 0; // 현재시각
        List<Integer> result = new ArrayList<>();
        List<Task> tasks = new ArrayList<>();
        
        for (int i = 0; i < jobs.length; i++) {
            tasks.add(new Task(jobs[i][0], jobs[i][1]));
        }
        
        // 요청시간이 이른순, 소요시간 짧은순으로 정렬.
        tasks.sort(
            (task1, task2) -> {
                int compareByRequestTime = Integer.compare(task1.getRequestTime(), task2.getRequestTime());
        
                if (compareByRequestTime != 0) {
                    return compareByRequestTime;
                } 
                else {
                    return Integer.compare(task1.getTurnaroundTime(), task2.getTurnaroundTime());
                }
            }
        );
        
        Deque<Task> waitQ = new ArrayDeque<>(tasks);
        
        // 하나의 작업이 실행되는 동안 이미 들어온 작업들은 소요시간 짧은 것 부터 우선적으로 처리.
        PriorityQueue<Task> readyQ = new PriorityQueue<>(
            (task1, task2) -> {
                int compareByTurnaroundTime = Integer.compare(task1.getTurnaroundTime(), task2.getTurnaroundTime());
        
                if (compareByTurnaroundTime != 0) {
                    return compareByTurnaroundTime;
                } 
                else {
                    return Integer.compare(task1.getRequestTime(), task2.getRequestTime());
                }
            }
        );
        
        while (!waitQ.isEmpty() || !readyQ.isEmpty()) {
            
            // 처리할 요청이 없으면 waitQ에서 하나 가져와서 처리.
            if (readyQ.isEmpty()) {
                curTime = waitQ.element().getRequestTime();
                readyQ.add(waitQ.remove());
            }
            
            Task task = readyQ.remove();
            result.add(curTime - task.getRequestTime() + task.getTurnaroundTime());
            curTime += task.getTurnaroundTime();
            
            // 하나의 작업을 처리하는 동안 들어온 요청들을 우선순위 큐에 넣어줌.
            while (!waitQ.isEmpty() && waitQ.element().getRequestTime() <= curTime) {
                readyQ.add(waitQ.remove());
            }
        }
        
        return (int)result.stream().mapToInt(Integer::intValue).average().orElse(0.0);
    }
}

1. 문제 정의
   요청 작업의 요청부터 완료까지 걸린 시간의 평균이 최소가 되도록 하는 문제이다.
   

2. 시간복잡도 계산
   jobs 배열의 크기가 최대 500이다.

3. 문제 풀이
   하나의 요청이 처리되는 동안 들어온 요청들이 기준에 정렬된 상태를 유지해야 되기 때문에 우선순위 큐를 사용했다. 우선순위 큐의 정렬 기준은 소요시간이 짧은순, 요청시간이 이른순으로 정의했다.

   그 이유는 이미 들어온 요청에 대해서 소요시간이 짧은거 부터 처리해야 다른 요청들이 덜 기다려서 전체 평균 처리시간이 짧아지기 때문이다.

4. 예외 사항
   기타 예외 사항 없음.