[PG] 디스크 컨트롤러 JAVA

programmers.co.kr/learn/courses/30/lessons/42627

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

각 작업의 [작업 요청 시간, 수행 시간]이 담긴 int[][] jobs가 주어진다.

SJF(Shortest Job First) 알고리즘으로 작업들을 수행하였을 때 작업들의 평균 대기시간을 반환해야한다.

(대기시간 = 작업 완료 시간 - 작업 요청 시간)

 

 

풀이 .

import java.util.*;

class Work {
    int arrive;
    int require;
    public Work(int arrive, int require) {
        this.arrive = arrive;
        this.require = require;
    }
}

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;

        // 시간의 흐름을 하나 두자
        // 현재 시간에서 도착한 놈들끼리 SJF를 수행하면 된다.
        // 1. pqArrive에 다 떄려넣는다.
        // 2. 그 중에서 arrive가 time을 넘긴 것만(이미 도착한 것만) pqRequire로 넘긴다.
        // 3. pqRequire 가지고 SJF 수행.
        PriorityQueue<Work> pqArrive = new PriorityQueue<>(new Comparator<Work>() {
            @Override
            public int compare(Work o1, Work o2) {
                return o1.arrive < o2.arrive ? -1 : 1;
            }
        });
        PriorityQueue<Work> pqRequire = new PriorityQueue<>(new Comparator<Work>() {
            @Override
            public int compare(Work o1, Work o2) {
                return o1.require < o2.require ? -1 : 1;
            }
        });

        for(int[] job : jobs) {
            pqArrive.add(new Work(job[0], job[1]));
        }

        int time = 0;
        int wait = 0;
        while(!(pqArrive.isEmpty() && pqRequire.isEmpty())) {
            // 도착한 작업 이동
            // !pqArrive.isEmpty() 없으면 에러. 남아있는 작업이 있어야 넘길 수도 있음
            while(!pqArrive.isEmpty() && pqArrive.peek().arrive <= time) {
                pqRequire.add(pqArrive.poll());
            }

            // SJF
            if(pqRequire.isEmpty()) {  // 도착한 작업 없으면 다음 작업 도착할 시간으로 이동
                time = pqArrive.peek().arrive;
            } else {
                int arrive = pqRequire.peek().arrive;
                int require = pqRequire.poll().require;
                time += require;
                wait += time - arrive;
            }
        }

        answer = wait / jobs.length;
        return answer;
    }
}

작업 요청시간과(arrive) 수행시간을(require) 한 번에 관리하기 위해 class Work을 만들었다.

정렬 기준이 다른 두개의 PriorityQueue를 사용한다. 하나는 요청시간, 하나는 수행시간을 기준으로 한다.

 

1. 도착하기 전 Work들은 모두 pqArrive에 담긴다.

2. 요청된 작업들은 pqRequire로 넘어간다.

3. SJF 수행

4. 요청한 작업이 아무것도 없을 경우를 고려해야한다. 아무것도 도착하지 않았다면 바로 다음 작업이 요청되는 시간으로 이동한다.