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

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

프로그래머스

모든 작업들의 평균 작업시간을 작게 만들어야 하는 문제이다. 운영체제에서 CPU 스케줄링에서 배운 최단작업 우선 스케줄링 기법(SJF)이 생각났는데, 그대로 하면 된다! 아이디어를 떠올리는 건 괜찮았는데, 구현이 어려웠고 자꾸 8번과 18번 테스트 케이스에서 실패해서 고생한 문제이다. 주요 포인트는 다음과 같다.

• 현재 시간까지 들어온 작업들을 큐에 넣는다. 그런데 이때 매개변수로 주어지는 jobs는 요청시간이 빠른 순서대로 정렬되어 있지 않다. 따라서 이를 que1에 넣고, que1을 요청시간을 기준으로 오름차순 해주었다.
• 이제 현재 시간까지 들어온 작업들을 que1에서 que2로 옮기면 된다.
• 그리고 que2는 소요시간을 기준으로 오름차순 해주었고, que2에 있는 작업들 중 소요시간이 가장 적은 작업을 우선으로 수행하면 된다.

위 로직대로 구현만 잘..! 하면 된다. 그런데 주의할 점은 내 코드에서 첫 번째 작업을 먼저 수행하고 그 뒤부터 while문을 타게 되는데, 만약 요청시간이 15, 소요시간이 34인 [15, 34]작업과 요청시간이 15, 소요시간이 2인 [15, 2]작업이 들어왔을 때, [15, 34]인 작업을 첫 번째 작업으로 취급하게 된다면, 현재 시간인 now 변수가 49(15+34)가 된다. 그리고 나서 while문을 타게 되면서 원하는대로 결과가 나오지 않는다. 따라서 que1에서 요청시간을 기준으로 오름차순을 정렬할 때, 요청시간이 같다면 소요시간을 기준으로도 오름차순 정렬을 해줘야 한다.

 

이에 대한 테스트 케이스는 다음과 같다. 

• jobs: [[24, 10], [28, 39], [43, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]]
• return: 72

내가 생각한 로직에서 예외 상황을 찾는 것이 참 어렵다.. 정렬을 했을 때 "만약 정렬 기준이 같다면? 같으면 또 다른 기준으로 정렬을 해줘야하지 않는지?"를 고려해보자.

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        
        // que1: 요청순서를 기준으로 오름차순
        Queue<Job> que1 = new PriorityQueue(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                // 주의!!! 요청시간이 같으면, 소요시간이 짧은 것이 먼저 처리되도록
                if (o1.start == o2.start) {
                    return o1.time - o2.time;
                }
                return o1.start - o2.start;
            }
        });
        
        for (int[] job : jobs) {
            que1.add(new Job(job[0], job[1]));
        }
        
        // que2: 소요시간을 기준으로 오름차순
        Queue<Job> que2 = new PriorityQueue(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                // 소요시간이 같으면, 먼저 요청된 것이 먼저 처리되도록
                if (o1.time == o2.time) {
                    return o1.start - o2.start;
                }
                return o1.time - o2.time;
            }
        });
        
        // 첫 번째 작업 수행
        Job poll = que1.poll();
        int now = poll.start + poll.time;
        int sum = now - poll.start;
        
        while (!que1.isEmpty() || !que2.isEmpty()) {
            
            // 현재 시간까지 들어온 요청을 que에 넣기
            while (!que1.isEmpty()) {
                if (now < que1.peek().start) {
                    break;
                } 
                que2.add(que1.poll());
            }
            
            // 만약 요청이 안들어왔으면, 다음 요청까지 시간 보내기
            if (que2.isEmpty()) { 
                now = que1.peek().start;
                continue; // continue를 해서 바뀐 현재 시간을 기준으로 다시 que1의 작업들을 que2로 넣어줘야 함
            }
        
            // que2에 있는 작업들 중 소요시간이 가장 작은 작업 수행하기
            Job job = que2.poll();
            now += job.time;
            sum += now - job.start;
        }
        return sum / jobs.length;
        
    }
    
    class Job {
        int start;
        int time;
        public Job (int start, int time) {
            this.start = start;
            this.time = time;
        }
    }
}