프로그래머스 디스크 컨트롤러 자바 풀이

문제 링크

문제 풀이 시간 : 50분

문제 요약

하드디스크는 한 번에 하나의 작업만 수행할 수 있다.
디스크 컨트롤러는 다음과 같은 우선순위로 작업을 처리한다:
모든 작업의 평균 반환 시간(요청~완료까지의 시간) 의 정수 부분을 구하라.

문제 풀이

이 문제는 보자마자 우선순위 큐를 써야겠다는 생각이 들었다.

하지만, 단순히 요청 시각이 빠른 순으로 정렬한다면, 아직 요청되지 않은 작업이 현재 작업보다 소요시간이 짧다는 이유로 먼지 처리되는 문제가 생길 수 있다.

그래서 나는 우선순위 큐를 두개 사용했다.

temp 큐 : 요청 시각을 기준으로 정렬
pq 큐 : 문제의 우선순위를 기준으로 정렬

이렇게 하면 현재 작업이 끝날 때까지 들어온 요청들을 pq에 쌓아두고 pq에서 우선순위가 높은 작업들을 선택해 처리할 수 있게 된다.

모든 작업을 요청 시각 기준으로 temp 큐에 저장
현재 시간(time)을 기준으로
pq가 비었다면,
pq에서 작업을 하나 꺼내 처리하고,
모든 작업을 처리할 때까지 반복

최종 코드

java

import java.util.*;

class Solution {
    public class Job{
        public int num;
        public int requestTime;
        public int jobTime;
        
        public Job(int num, int requestTime, int jobTime){
            this.num = num;
            this.requestTime = requestTime;
            this.jobTime = jobTime;
        }
    }
    
    public int solution(int[][] jobs) {
        int answer = 0;
        int cnt = jobs.length;
        
        // 우선순위: 작업시간 -> 요청 시각 -> 작업 번호
        PriorityQueue<Job> pq = new PriorityQueue<>((o1, o2)->{
            if(o1.jobTime == o2.jobTime && o1.requestTime == o2.requestTime)
                return o1.num - o2.num;
            else if(o1.jobTime == o2.jobTime)
                return o1.requestTime - o2.requestTime;
            else
                return o1.jobTime - o2.jobTime;
        });
        
        // 요청 시각 기준 정렬
        PriorityQueue<Job> temp = new PriorityQueue<>((o1, o2)->{
            return o1.requestTime - o2.requestTime;
        });
        
        for(int i=0;i<cnt;i++){
            temp.add(new Job(i, jobs[i][0], jobs[i][1]));
        }
        
        int time = 0;
        while(!pq.isEmpty() || !temp.isEmpty()){
            // 작업 우선순위 큐가 비어있다면, 
            // 현재 시간 이후 처음 요청된 작업들을 넣어줌
            if(pq.isEmpty()){
                pq.add(temp.poll());
                while(!temp.isEmpty() && temp.peek().requestTime == pq.peek().requestTime)
                    pq.add(temp.poll());
            }
            
            Job now = pq.poll();
            // 현재 작업을 기준으로 시간 업데이트
            time = Math.max(time, now.requestTime); // 요청 시각 이전이면 시간 맞추기
            time += now.jobTime; // 작업 수행
            answer += time-now.requestTime; // 반환 시간 누적
            
            // 현재 작업 중 새로 요청된 작업들을 pq로 이동
            while(!temp.isEmpty() && temp.peek().requestTime <= time){
                pq.add(temp.poll());
            }
        }
        
        return answer/cnt;
    }
}

디스크 컨트롤러

문제 풀이 시간 : 50분

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기