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

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

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

 

풀이

 

이 문제는 우선순위큐 2개를 사용해서 풀이하였습니다.

• 작업의 요청 시간을 기준으로 오름차순 정렬되는 우선순위 큐 : pq1
• 작업의 소요 시간을 기준으로 오름차순 정렬되는 우선순위 큐 : pq2

이렇게 두가지 우선순위 큐를 적절하게 이용하면서 문제를 해결해야 합니다.

 

1. 모든 작업들을 요청 시간을 기준으로하는 pq1에 넣어줍니다.
2. 현재 시간 = 0인 시점부터 pq1이 empty가 될 때 까지 다음을 반복합니다.
   1. 현재 시간 까지 요청된 작업들을 모두 pq1에서 꺼내 소요시간을 기준으로 하는 pq2에 넣어줍니다.
   2. 더 이상 현재 시간 까지 요청된 작업이 없는 경우 pq2에 대해 연산을 수행합니다.
      • pq2가 empty인 경우 : 현재 시간에 수행가능한 작업이 없으므로 현재시간++
      • pq2가 empty가 아닌 경우 : pq2의 peek에 있는 작업을 수행하고 현재시간과 answer값을 업데이트
        
        • 현재 시간 = 현재시간 + peek 작업의 소요 시간
        • answer = answer + (현재시간 - peek작업의 요청 시간)
3. pq2에 아직 남아있는 작업이 존재할 수 있으므로 나머지 작업을 수행하면서 현재시간과 answer값을 업데이트합니다.
4. 마지막으로 answer = answer / (전체 작업 수)를 해주면 풀이 끝! 

 

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        //요청 시간 기준 오름차순
        PriorityQueue<Task> pq1 = new PriorityQueue<>();
        //소요 시간 기준 오름차순
        PriorityQueue<Task> pq2 = new PriorityQueue<>();
        
        
        //모두 시작시간 기준 우선순위 큐에 넣어줌
        int len = jobs.length;
        for(int i=0; i<len; i++){
            pq1.add(new Task(jobs[i][0], jobs[i][1]));
        }
        
        //현재 시간과 비교하여 수행가능한 일들을 다른 우선순위큐에 넣음
        int now = 0;
        while(!pq1.isEmpty()){
            Task t = pq1.peek();
            int sTime = t.first;
            int tTime = t.second;
            
            //현재 시간 이전에 요청된 작업이 소요시간 기준이 되도록 pq2에 넣어줌
            if(sTime <= now){
                pq1.remove();
                pq2.add(new Task(tTime, sTime));
                
            }
            //현재 시간에 수행 가능한 작업 모두 pq2에 넣은 경우 -> pq2에서 하나 뽑아 실행
            else{
                //현재 시간에 수행 가능한 작업 없음 -> 시간 증가 시킴
                if(pq2.isEmpty())
                    now++;
                //pq2의 작업 중 시간 가장 적게 걸리는 것 수행
                else{
                    t = pq2.peek();
                    tTime = t.first;   //소요 시간
                    sTime = t.second;   //시작 시간
                    pq2.remove();
                    now = now + tTime;
                    answer = answer + (now - sTime);
                }
            }
        }
        
        //pq2에 남은 작업 있는 경우 수행
        while(!pq2.isEmpty()){
            Task t = pq2.peek();
            int tTime = t.first;   //소요 시간
            int sTime = t.second;   //시작 시간
            pq2.remove();
            now = now + tTime;
            answer = answer + (now - sTime);
        }
        
        answer = answer / len;
        return answer;
    }
    
    
}

class Task implements Comparable<Task> {
    int first, second;
    
    Task(int first, int second) {
        this.first = first;
        this.second = second;
    }
    
    public int compareTo(Task t) {
        if(this.first < t.first) {
            return -1; // 오름차순
        }
        else if(this.first == t.first) {
            if(this.second < t.second) {
                return -1;
            }
        }
        return 1;
    }
}