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

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/4262

🤔 문제

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

예를들어

• `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)`

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

📌 제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

😮 문제 해결 방법

디스크 컨트롤러 문제는 OS의 스케줄링 방법 중 하나인 SJF(Shortest Job First)방식중 비선점 방식과 동일한 문제이다.

따라서, 디스크가 작업 중에 다른 경과시간이 짧은 작업이 들어와도 우선 처리한 후 그 다음 짧은 작업을 실행한다.

그러므로, 디스크 컨트롤러 문제 해결의 핵심 포인트는 jobs배열의 시작 시간이 빠른 순으로 정렬하는 점과 우선순위 큐를 비교할때 경과 시간 순으로 큐에 삽입해주는 것이다.

static class Disk implements Comparable<Disk> {
        private int start;      //시작 시간
        private int elapsed;    //경과 시간

        public Disk(int start, int elapsed) {
            this.start = start;
            this.elapsed = elapsed;
        }

        public int getStart() {
            return start;
        }

        public int getElapsed() {
            return elapsed;
        }

        // 경과 시간이 짧은 순서로 힙에 넣어줌
        @Override
        public int compareTo(Disk o) {
            if (this.elapsed < o.elapsed) return -1;
            else if (this.elapsed > o.elapsed) return 1;
            return 0;
        }
    }

start(시작시간)과 elapsed(경과시간)을 변수로 가지는 Disk 클래스를 생성한다. Disk 클래스는 Comparable 인터페이스를 경과시간이 짧은 순으로 큐에 넣어주기 위해서 구현해주었다.

{{4, 9},{5, 6},{1, 1}}라는 원소를 가진 jobs배열을 예시로 들어보자.

우선적으로 해당 배열을 시작 시간 즉, 4, 5, 1을 정렬해 주어야한다. (시작시간이 짧은 순)

{{1, 1},{4, 9},{5, 6}}로 정렬이 마무리 되면 우선순위 큐에 가장 먼저 시작하는 작업을 넣어준다.

작업이 완료된 후 주의할 점은 현재 작업이 완료되었을 때 아직 시작시간이 되지 않은 작업이 한개도 없다면 가장 먼저 요청한 작업이 실행한다는 점이다.

따라서, while문의 조건에는 큐가 비어있지 않거나 아직 jobs에 작업이 남아있다면 계속해서 반복하는 조건을 주어야한다. 1초에 시작한 작업이 1초 경과후 2초에 끝나지만 그 다음 작업은 4초에 시작하고 아직 작업이 남아있기 때문에 큐가 비어도 계속해서 while문을 접근해야 한다.

//큐가 empty가 아니거나 아직 작업이 큐에 다 들어가지 않은 경우
while (!pq.isEmpty() || list.size() > 0) {

첫 번째 작업이 시작되는 시점을 현재 시간(time 변수)에 넣어주고 작업이 완료될 때마다 경과 시간을 더해주면 진행중인 작업이 끝난 현재 시간이 된다.

이후 현재 시간보다 요청 받은 작업이 배열에 남아있다면 큐에 모두 넣어준다. 그리고 작업을 반복하면 스케줄링에 걸린 모든 시간을 구할 수 있고, 작업의 갯수로 나눠주면 평균 작업시간이 나오고 return해주면 문제가 해결된다.

아래는 Java로 구현한 코드이다.

🚩 JAVA 코드

package com.algorithm.Programmers.Lv3;

import java.util.*;

public class Solution_42627 {
    static class Disk implements Comparable<Disk> {
        private int start;      //시작 시간
        private int elapsed;    //경과 시간

        public Disk(int start, int elapsed) {
            this.start = start;
            this.elapsed = elapsed;
        }

        public int getStart() {
            return start;
        }

        public int getElapsed() {
            return elapsed;
        }

        // 경과 시간이 짧은 순서로 힙에 넣어줌
        @Override
        public int compareTo(Disk o) {
            if (this.elapsed < o.elapsed) return -1;
            else if (this.elapsed > o.elapsed) return 1;
            return 0;
        }
    }

    public static void main(String[] args) {
        int[][] jobs = {{1, 1}, {4, 9}, {5, 6}};
        System.out.println(solution(jobs));
    }

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

        PriorityQueue<Disk> pq = new PriorityQueue<>();

        //Jobs 배열을 시작시간이 빠른 순서로 먼저 정렬
        //시작시간이 동일한 경우 경과 시간이 짧은 순으로 정렬
        Arrays.sort(jobs, (o1, o2) -> {
            if (o1[0] == o2[0])
                return Integer.compare(o1[1], o2[1]);
            else
                return Integer.compare(o1[0], o2[0]);
        });

        LinkedList<Disk> list = new LinkedList<>();
        for (int[] job : jobs)
            list.add(new Disk(job[0], job[1]));

        pq.offer(list.poll());      //가장 빠른 작업 제일 먼저 넣어주기
        int time = pq.peek().getStart();     //가장 빠른 작업 시작시간이 모든 스케줄링 시작 시간

        //time >= start 인 값 큐에 넣기
        //time += elapsed;
        //answer += time - disk.start;
        //큐가 empty가 아니거나 아직 작업이 큐에 다 들어가지 않은 경우
        while (!pq.isEmpty() || list.size() > 0) {
            /*큐가 비었지만 list size가 남은 경우는 (1,1) (4,1)의 경우
             *1초에 시작 2초에 완료, 이후 2초부터 다음 작업 시작시간인 4초까지 작업이 없기 때문에
             *먼저 요청하는 작업 큐에 넣어주기
             */
            if(list.size() > 0 && pq.isEmpty()){
                time = list.peek().getStart();
                pq.offer(list.poll());
                continue;
            }
            Disk disk = pq.poll();
            time += disk.getElapsed();      //경과 시간을 더해주면 작업이 끝난 현재 시간

            while (list.size() > 0 && time >= list.peek().getStart()) {
                pq.offer(list.poll());      //현재 시간보다 전에 요청 받은 작업 큐에 넣어주기
            }
            answer += time - disk.getStart();   //현재 시간부터 요청 시작 시간을 빼주면 요청부터 작업 완료까지의 시간
        }

        return answer / jobs.length;
    }
}

📄 정리

• 운영체제 스케줄링 기법인 SJF 기법 중 Non-Preemtive(비선점) 방식을 사용한 문제이다. 스케줄링 기법에 대해 파악을 하고 있어서 문제 해결에 있어서 도움이 된 것 같다. 또한 스케줄링 기법에 대해 리마인드하는 계기가 되었다.
• 배열의 접근이 어려워 List를 생성해 코드를 구현했는데 배열로 파라미터가 주어졌기 때문에 해당 매개변수 내에서 해결하는 방식을 기를 필요가 있다고 생각한다.