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

문제 링크

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

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

풀이

 문제의 특성 상 작업이 오는 순서대로 처리해야 하며, 그러는 와중에 작업들의 소요시간(turn around time) 합의 평균이 가장 작아야 한다. 그렇기 때문에 작업들을 모두 한 곳에 모아 정리할 수 없고, 완전탐색 처럼 모든 경우의 수를 계산하기엔 요청이 500개 가까이 되기에 시간 초과의 위험이 생긴다. 그렇다면 해답은 마치 컴퓨터의 운영체제와 같이 특정 우선순위 큐를 만들어 작업이 들어올 때마다 해당 큐에 넣고 하나씩 큐에서 작업을 꺼내와 작업을 처리해야 한다.

 그렇다면 우선순위 큐에서 이루어질 객체 간의 비교 로직을 작성해야 하는데, 문제에서 주어지는 예시를 보았을 때는 해당 시점에서 처리시간이 가장 짧은 프로세스를 골라 처리를 하게 된다. 이에 착안해 작업에 대한 클래스 속 compareTo 함수를 이와 비슷하게 처리시간이 빠른 순으로, 처리시간이 같다면 작업 요청이 들어온 시간이 빠른 순으로 반환하는 것으로 작성했다.

 이후에는 인자로 들어오는 2차원 배열을 요청 도착 순으로 우선 정렬한 뒤, 맨 처음 작업을 처리하고 완료 시간을 기준으로 이보다 빨리 요청이 도착한 작업들을 우선 순위에 넣고 다음 시간으로 이동한다. 이후에는 동일하게 큐에서 작업을 하나 꺼내 작업을 처리하고, 해당 완료 시간보다 요청이 일찍 도착한 작업들을 골라 우선순위 큐에 넣는 것으로 코드를 작성했다. 그렇게 작업을 처리할 때마다 해당 작업의 요청 시간부터 완료 시간까지의 차이를 모두 저장한 다음 크기만큼 나누는 것을 해답으로 반환한다.

 

class Solution {
        public int solution(int[][] jobs) {
            int time = 0, totalTurnAroundTime = 0;

            PriorityQueue<Pair> pq = new PriorityQueue<>();
            Arrays.sort(jobs, new Comparator<int[]>() {//우선 요청 시간 순 정렬
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });

            for (int i = 0; i < jobs.length;) {//들어와 있는 모든 요청이 될 때까지
                while (i < jobs.length && time >= jobs[i][0]) {//현 시간보다 빠른 요청들은 모두 우선순위 큐에
                    pq.add(new Pair(jobs[i][0], jobs[i][1]));
                    i++;
                }

                if (!pq.isEmpty()) {//하나를 빼 계산 진행
                    Pair pair = pq.poll();
                    time += pair.processingTime;
                    totalTurnAroundTime += time - pair.startTime;
                } else {//큐가 비어있다면
                    time = jobs[i][0];//다음 요청에 시간 조정
                }
            }

            while (!pq.isEmpty()) {//큐에 남아있는 시간들 모두 처리
                Pair pair = pq.poll();
                time += pair.processingTime;
                totalTurnAroundTime += time - pair.startTime;
            }

            return totalTurnAroundTime / jobs.length;
        }

        class Pair implements Comparable<Pair> {// Pair 클래스 끼리의 비교
            int startTime, processingTime;

            public Pair(int startTime, int processingTime) {
                this.startTime = startTime;
                this.processingTime = processingTime;
            }

            @Override
            public int compareTo(Pair p) {
                if(this.processingTime < p.processingTime)
                    return -1;
                else if (this.processingTime == p.processingTime) {
                    if(this.startTime < p.startTime)
                        return -1;
                }

                return 1;
            }
        }
    }

결과