[ Programmers ][JAVA][42627] 디스크컨트롤러

프로그래머스 힙 - 디스크컨트롤러

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

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

 

처음 문제를 접했을 때는 가장 빠른 시간을 기준으로 정렬한 뒤 계산하는 greedy 알고리즘이 생각났다.

 

하지만 곧 문제유형이 Heap인 것을 보고 클래스를 정의하여 우선순위큐에 사용해야함을 인지했다. 하지만 나는 단순히 pq하나만 구현하여 그 안에서 정렬해준 뒤 계산하면 되는 줄 알았지만... 문제는 풀리지 않았고 ( 언제쯤 혼자 풀거냐 )

 

키포인트는 작업큐(PQ)뿐 아니라 대기큐(LinkedList)도 불러와서 사용해야 했다.

(출처 : velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC-Java )

 

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        //대기 큐
        LinkedList<Process> waiting = new LinkedList<>();
        
        //작업 큐
        PriorityQueue<Process> pq = new PriorityQueue<>(new Comparator<Process>() {
           public int compare(Process p1, Process p2){
               return p1.wt - p2.wt;
           } 
        });
        
        for(int[] job : jobs){
            waiting.offer(new Process(job[0], job[1]));
        }
        
        Collections.sort(waiting, new Comparator<Process>(){
            public int compare(Process p1, Process p2){
                return p1.rt - p2.rt;
            }
        });
        
        int answer = 0;
        int cnt = 0;
        int time = waiting.peek().rt;
        
        while(cnt < jobs.length){
            while(!waiting.isEmpty() && waiting.peek().rt <= time){
                pq.offer(waiting.pollFirst());
            }
            
            if(!pq.isEmpty()){
                Process process = pq.poll();
                time += process.wt;
                answer += time - process.rt;
                cnt++;
            } else{
                time ++;
            }
        }
        
        return answer / cnt;
    }
    
    class Process{
        int rt;
        int wt;
        
        public Process(int rt, int wt){
            this.rt = rt;
            this.wt = wt;
        }
    }
}

 

시간이 많다면 충분히 고민해보고 풀텐데 퇴근 시간 후 집에 있는 시간이 짧아 쉽지가 않다.. 우선 최대한 유형별로 까먹지 않는 것을 목표로 하자. 지금은 100% 이해가 안되니 내일 아침 출근해서 다시 보도록 하자