[알고리즘] 프로그래머스 - 디스크 컨트롤러(힙)

1. 문제

2. 문제 풀이

최대값이나 최소값을 뽑아내는 우선순위큐(힙)를 이용해서 문제를 풀었다. 우선 요청시간과 처리시간을 저장할 수 있도록 Job 클래스를 만들어서 데이터를 저장하게 하였다. Job의 정렬 기준으로는 처리 시간이 더 작은게 앞으로 오게 하였다. waitQueue에는 현재 시간과 비교해서 하나의 작업이 끝났을 때 요청 시간이 현재 시간보다 작거나 같으면 waitQueue에 저장을 하였다.

1. 주어진 jobs 배열을 요청 시간에 대해서 오름차순으로 정렬한다.
2. 모든 job을 waitQueue에 넣고, 대기큐(waitQueue)에 job이 없을때까지 반복문을 실행한다.
3. waitQueue에 작업을 넣지 않았고, 현재 시간이 작업 요청 시간보다 작거나 같으면 waitQueue에 job을 넣어준다.
4. waitQueue가 비어있지 않다면 작업 요청 시간이 가장 적은 job을 꺼내서 time에 처리시간 만큼 더해주고, 요청부터 처리 완료된 시간을 누적해서 더해준다.
5. 작업은 있으나 아직 요청 시간에 도달하지 않았으면 time을 1씩 증가시켜준다.

문제를 풀면서 하나 기억할만한 것은 우선순위 큐에 Comparable을 구현한 Job 객체를 넣으면 알아서 정렬이 되었다. 따로 Collection.sort를 호출하지 않아도 된다.(호출하면 에러남)

import java.util.*;

class Solution {

    PriorityQueue<Job> waitQueue = new PriorityQueue<>();
    Boolean[] visit;
    
    int time = 0;
    int totalReqAvgTime = 0;
    
    public void addWaitQueue(int[][] jobs){
        int size = visit.length;
        for(int i=0;i<size;i++){
            if(time>=jobs[i][0] && visit[i] == false){
                waitQueue.add(new Job(jobs[i][0], jobs[i][1]));
                visit[i] = true;
            }
        }
    }
    
    public Boolean isAllVisit(){
        int size = visit.length;
        for(int i=0;i<size;i++){
            if(visit[i] == false)
                return false;
        }
        return true;
    }
    
    public int solution(int[][] jobs) {

        visit = new Boolean[jobs.length];
        
        //Visit 배열 초기화
        for(int i=0;i<jobs.length;i++){
            visit[i] = false;
        }
        
        //배열 요청 시간순으로 정렬
        Arrays.sort(jobs, new Comparator<int[]>(){
            @Override
            public int compare(int[] j1, int[] j2){
                return j1[0] - j2[0];
            }
        });

        while(!(isAllVisit() == true && waitQueue.isEmpty())){
            addWaitQueue(jobs);
            if(!waitQueue.isEmpty()){
                Job front = waitQueue.poll();
                time += front.getPrcTime();
                totalReqAvgTime += time - front.getReqTime();
            } else{
                time++;
            }
        }
        
        return totalReqAvgTime/jobs.length;
    }
    
    class Job implements Comparable<Job>{
        
        private int reqTime;
        private int prcTime;
        
        public int getPrcTime(){
            return this.prcTime;
        }
        
        public int getReqTime(){
            return this.reqTime;
        }
        
        public Job(int reqTime, int prcTime){
            this.reqTime = reqTime;
            this.prcTime = prcTime;
        }
        
        @Override
        public int compareTo(Job job){
            return this.prcTime - job.getPrcTime();
        }
    }
}

풀이시간이 생각보다 오래걸렸는데 그 이유는 다양한 케이스를 고려하지 못했다. 처음에 무조건 0초에 데이터가 들어올꺼라고 생각했던 점과 비어있는 시간이 있을꺼라고 생각을 하지 못했다. 다양한 반례 케이스에 대해서 생각하는 사고력을 증가시킬필요를 느꼈다.