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

문제 설명

 

프로그래머스

 

접근 방법

해당 문제는 우선순위 큐를 활용하여 해결할 수 있었습니다.

 

문제 조건 분석

문제에서는 각 작업별로 최초 요청 시간과 작업 시간이 주어졌을 때, 각 작업별로 요청되는 시간부터 작업이 종료되는 시간(이하 '처리 시간' = 대기 시간 + 실행 시간)의 '최소' 평균을 요구하고있습니다. 이때 각 작업별 처리 시간 동안 작업의 상태를 다음과 같이 나타내볼 수 있겠습니다.

 

 

여기서 실행 시간은 고정되어있는 값으로, 각 작업별 처리 시간의 최소 평균을 구하기 위해서는 대기 상태를 최대한 줄이는 노력이 필요합니다. 이때 대기 상태를 줄이기 위해서는 실행 시간이 적은 작업을 우선적으로 처리해야합니다.

 

예를 들어, 동시에 요청된 작업인 A(작업 시간이 10초)와 B(작업 시간이 20초)가 있다고 가정해보겠습니다. 만일 B가 먼저 실행된다면, B의 처리 시간은 20초(대기 시간 0초, 실행 시간 20초)이겠으나, A의 처리 시간은 30초(대기 시간 20초, 실행 시간 10초)로, 처리 시간 평균은 25초입니다.

 

 이번엔 반대로 A가 먼저 실행된다면, A의 처리 시간은 10초(대기 시간 0초, 실행 시간 10초), B의 처리 시간은 30초(대기 시간 10초, 실행 시간 20초)로, 처리 시간 평균은 20초입니다. 즉, B가 먼저 실행했을 때보다 처리 시간 평균이 5초 빠릅니다.

 

다만, 문제 조건 상 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리하도록 하고 있습니다.

 

소스코드 구현

이제 이러한 정렬 조건들을 반영한 우선순위 큐를 다음과 가이 선언해주도록 합니다.

 

    static class Job implements Comparable<Job> {
        int requestTime;
        int workTime;
        int startTime;

        public Job(int requestTime, int workTime) {
            this.requestTime = requestTime;
            this.workTime = workTime;
            this.startTime = requestTime;
        }

        public int getTotalTime() {
            return workTime + startTime - requestTime;
        }

        @Override
        public int compareTo(Job o) {
            if (this.startTime != o.startTime) {
                return this.startTime - o.startTime;
            }

            return this.workTime - o.workTime;
        }
    }
    
    public int solution(int[][] jobs) {
        int totalJobCount = jobs.length;
        int totalTimeByJobs = 0;

        PriorityQueue<Job> queue = new PriorityQueue<>();
        for (int[] job : jobs) {
            queue.add(new Job(job[0], job[1]));
        }
        
        // ...

 

별도의 Job 클래스를 정의했는데, 인자로 주어지는 요청 시간(request time)과 실행 시간(work time)과 함께 이와 별개로 실제로 작업이 시작되는 시간(start time)을 저장해주도록 했습니다. 이때 작업 시작 시간은 최초 요청 시간으로 초기화해줬는데, 이는 우선적으로 먼저 요청이 들어온 작업을 처리해주기 위함입니다.

 

정렬 조건(compareTo 메서드 구현)은 앞서 분석했던 조건들을 바탕으로 작업 시작 시간이 가장 빠른 작업들을 우선적으로 처리해주되, 작업 시작 시간이 같다면, 실행 시간이 가장 적은 것을 우선적으로 처리해주도록 했습니다.

 

---

 

Job 객체들이 모두 우선순위 큐에 저장이 된 후에는 이제 우선순위가 가장 높은 Job 객체부터 빼내(poll) 이를 처리해주도록 합니다.

 

        int presentTime = 0;

        while (!queue.isEmpty()) {
            Job job = queue.poll();

            if (job.startTime >= presentTime) {
                presentTime = job.startTime + job.workTime;
                totalTimeByJobs += job.getTotalTime();
            } else {
                job.startTime = presentTime;
                queue.add(job);
            }
        }

        return totalTimeByJobs / totalJobCount;

 

이때 앞서 요청 시간으로 초기화했던 작업 시작 시간(start time)이 현재 시간(present time, 마지막으로 작업이 처리된 시간) 보다 크거나 같은 경우 현재 디스크에서 처리 중인 작업이 없는 것으로 볼 수 있으므로, 작업을 처리해주도록 합니다. 여기서 현재 시간(present time)을 작업이 처리가 완료된 시간(start time + work time)으로 초기화 해주고, 작업별 처리 시간(totalTimeByJobs)에는 해당 작업의 처리 시간(work time + start time - request time)을 더해주도록 합니다.

 

반면에, 앞서 요청 시간으로 초기화했던 작업 시작 시간(start time)이 현재 시간(present time, 마지막으로 작업이 처리된 시간) 보다 작은 경우에는 해당 작업의 시작 시간을 현재 시간으로 초기화 해준 후 다음에 처리하도록 다시 큐에 집어 넣습니다.(add)

 

모든 작업들이 처리된 이후 최종적으로 작업의 개수(jobs.length)로 작업 전체 처리 시간(totalTimeByJobs)를 나눈 값을 반환해줍니다.

 

나의 소스 코드

import java.util.PriorityQueue;

class Solution {

    static class Job implements Comparable<Job> {
        int requestTime;
        int workTime;
        int startTime;

        public Job(int requestTime, int workTime) {
            this.requestTime = requestTime;
            this.workTime = workTime;
            this.startTime = requestTime;
        }

        public int getTotalTime() {
            return workTime + startTime - requestTime;
        }

        @Override
        public int compareTo(Job o) {
            if (this.startTime != o.startTime) {
                return this.startTime - o.startTime;
            }

            return this.workTime - o.workTime;
        }
    }

    public int solution(int[][] jobs) {
        int totalJobCount = jobs.length;
        int totalTimeByJobs = 0;

        PriorityQueue<Job> queue = new PriorityQueue<>();
        for (int[] job : jobs) {
            queue.add(new Job(job[0], job[1]));
        }

        int presentTime = 0;

        while (!queue.isEmpty()) {
            Job job = queue.poll();

            if (job.startTime >= presentTime) {
                presentTime = job.startTime + job.workTime;
                totalTimeByJobs += job.getTotalTime();
            } else {
                job.startTime = presentTime;
                queue.add(job);
            }
        }

        return totalTimeByJobs / totalJobCount;
    }

 

참고자료

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