[프로그래머스] 디스크 컨트롤러 (Java)

문제

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

코딩테스트 연습 - 디스크 컨트롤러

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

풀이

우선순위 큐를 두 개 만들어서 풀었다. 

대기 큐 : 요청 순으로 정렬 

실행 큐: 프로세스가 짧은 순으로 정렬 

 

1. 요청 배열의 정보를 대기큐에 담는다.

2. 대기큐가 empty 상태가 될 때까지 while문을 진행한다. 

3. 대기큐에서 현재 시각에 실행 할 수 있는 프로세스를 뽑아서 실행큐에 넣는다. 

4. 실행할 프로세스가 없다면 현재시간을 +1 증가시킨다. 

5. 실행할 프로세스가 있다면 그 중 가장 짧은 프로세스를 실행시켜서 경과시간을 저장하고 현재시간을 업데이트한다. 

6. 현재 시간이 업데이트 되었기 때문에 현재 실행 가능한 프로세스를 다시 뽑아야 하므로, 실행큐에 있는 데이터를 다시 대기큐에 넣는다. 

 

소스코드

import java.util.*;
class Process {
    int reqTime; 
    int processTime;
    
    public Process(int reqTime, int processTime){
        this.reqTime = reqTime;
        this.processTime = processTime;
    } 
    
    public boolean canStart(int curTime){
        if(this.reqTime <= curTime){
            return true;
        }
        return false;
    }
}

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        PriorityQueue<Process> waitQueue = new PriorityQueue<Process>(new Comparator<Process>(){
            @Override
            public int compare(Process p1, Process p2){
                return p1.reqTime - p2.reqTime;
            }
        });
        PriorityQueue<Process> runQueue = new PriorityQueue<Process>(new Comparator<Process>(){
            @Override
            public int compare(Process p1, Process p2){
                return p1.processTime - p2.processTime;
            }
        });
        
        for(int i = 0; i < jobs.length; i++){
            // 대기 큐에 프로세스를 담는다.
            // 요청 시간 순으로 정렬
            waitQueue.offer(new Process(jobs[i][0], jobs[i][1]));
        }
        
        int totalTime = 0;
        int curTime = 0;
        while(!waitQueue.isEmpty()){           
            // 대기큐에 있는 프로세스 중 현재 시각에 실행 할 수 있는 프로세스를 모두 실행 큐에 넣는다.
            while(!waitQueue.isEmpty()){
                Process waitP = waitQueue.peek();
                if(waitP.canStart(curTime)){
                    runQueue.offer(waitQueue.poll());
                } else {
                    break;
                } 
            }
            
            // 실행할 프로세스가 없다면 시간을 증가시킨다.
            if(runQueue.isEmpty()){
                curTime++; 
                continue;
            }
            
            // 실행할 프로세스가 있다면 처리 시간이 짧은 프로세스를 실행하여 경과 시간을 계산한다.      
            Process runP = runQueue.poll();
            totalTime += (curTime - runP.reqTime) + runP.processTime;
            curTime = curTime + runP.processTime;
            
            // 나머지는 다시 대기큐에 넣음. curTime이 달라지기 때문에 해당 시간에 실행할 수 있는 프로세스 뽑는 걸 다시 진행 해야함
            while(!runQueue.isEmpty()){   
                waitQueue.offer(runQueue.poll());
            } 
        }

        return totalTime/jobs.length;
    }
}