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

문제 : programmers.co.kr/learn/courses/30/lessons/42627

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

"작업의 요청부터 종료까지 걸린 시간의 평균"을 최소화 하기 위해서는 Shortest Job First로 Job scheduling을 해 주어야 한다.

또, 문제에 주어진 조건에서 하드디스크가 idle 상태일 때에는 먼저 들어온 작업부터 처리해야 하므로 이 부분도 같이 고려해야 한다.

 

이는 두 개의 priority queue를 사용하여 해결할 수 있다.

이 두 개의 priority queue를 각각 wait queue와 job queue라고 하면, wait queue는 job의 요청 시간을 오름차순으로 정렬하고, job queue는 job의 작업시간을 오름차순으로 정렬하도록 한다.

이후 현재시간 n에 대해서 (n은 0부터 시작) wait queue에서 n보다 이른 시점에 요청된 job들을 모두 꺼내 job queue에 offer해 준다. 이 과정을 해준 후 job queue가 empty 상태라면 wait queue의 첫 번째 원소의 요청시간으로 현재시간을 업데이트한다.

job queue가 empty 상태가 아니면 그대로 poll을 하여 작업을 수행하고, 이 job의 요청시간, 소요시간을 확인하여 총 작업시간 및 현재 시간을 적절히 업데이트 해 준다.

이를 총 작업 수에 맞게 반복하면 올바른 결과를 도출할 수 있다.

 

이를 순서도로 표현하면 아래 그림과 같다.

 

디스크 컨트롤러 문제풀이 흐름도

 

소스코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        HardDiskSystem hddSystem = new HardDiskSystem();
        hddSystem.insertJobs(jobs);
        hddSystem.doJobScheduling();
        return hddSystem.getTotalElapsedTime() / jobs.length;
    }
}

class Job {
    private int requestedTime;
    private int workTime;

    Job(int requestedTime, int workTime) {
        this.requestedTime = requestedTime;
        this.workTime = workTime;
    }

    public int getRequestedTime() {
        return this.requestedTime;
    }

    public int getWorkTime() {
        return this.workTime;
    }
}

class HardDiskSystem {
    private PriorityQueue<Job> waitQueue; // request time 기준. 오름차순 정렬
    private PriorityQueue<Job> jobQueue; // work time 기준. 오름차순 정렬
    private int currentTime;
    private int totalElapsedTime;
    private int totalJobNumber;
    private int countJobDone;

    HardDiskSystem() {
        waitQueue = new PriorityQueue<>(Comparator.comparingInt(Job::getRequestedTime));
        jobQueue = new PriorityQueue<>(Comparator.comparingInt(Job::getWorkTime));
        currentTime = 0;
        totalElapsedTime = 0;
        countJobDone = 0;
    }

    public int getTotalElapsedTime() {
        return totalElapsedTime;
    }

    public void insertJobs(int[][] jobs) {
        for (int[] job : jobs) {
            waitQueue.offer(new Job(job[0], job[1]));
        }
        totalJobNumber = waitQueue.size();
    }

    public void doJobScheduling() {
        while (countJobDone < totalJobNumber) {
            // Schedule jobs to do
            while (!waitQueue.isEmpty() && waitQueue.peek().getRequestedTime() <= currentTime) {
                jobQueue.offer(waitQueue.poll());
            }

            if (jobQueue.isEmpty()) {
                currentTime = waitQueue.peek().getRequestedTime();
                continue;
            }

            // do a job scheduled
            Job currentJob = jobQueue.poll();
            currentTime += currentJob.getWorkTime();
            totalElapsedTime += (currentTime - currentJob.getRequestedTime());
            countJobDone++;
        }
    }
}