(코테) 프로그래머스_디스크 컨트롤러 * 힙 우선순위

 

문제 링크

 

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

 

 

정답

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int count = 0;
        
        //임시 담는 큐
        Queue<int[]> q =new LinkedList<>();
    
        Arrays.sort(jobs,(a,b) -> a[0] - b[0] );      

        for(int i=0;i<jobs.length;i++){            
            q.offer(jobs[i]);
        }
        
         //우선순위큐
        PriorityQueue<int[]> pq= new PriorityQueue<>((a,b)-> a[1]-b[1]);
        
        int nowRound=0;
        int done =0;    
        
        
        
        //for(int i=0;i<jobs.length;i++){
        while(done < jobs.length ){
            //pq.offer(q.peek());                         
            
            //우선순위 큐에 담아줌 
            while(!q.isEmpty() && nowRound >= q.peek()[0] ){
                pq.offer(q.poll());                
            }
            
            //위 while문 조건에 안맞아 우선순위 큐에 못담았으면 시작 시간 맞춰줌  (시작 시간 텀 잇으면)
            if(pq.isEmpty()){
                nowRound = q.peek()[0]; 
                continue;
            }
            
            
            //pq에서 꺼내서 축적 시켜줌 
            int[] pqCurrent=pq.poll();
            int pStart =pqCurrent[0];
            int pTime =pqCurrent[1];
            int diff=nowRound-pStart;
            
            nowRound+=pTime;
            
            if(diff>0) count += (diff+pTime);
                else  count += pTime;                        
            
            
            //작업한 횟수 카운팅
            done++;
        }
        
        
        //평균 반환
        return count/jobs.length;
    }
}

 

 

 

회고.

1. 문제 파악 미스. 작업 마친 시점에서  시간을 기준으로 우선 순위큐에 담아야한다. 
난 미리 배열로 작업 걸리는 시간 순으로 리스트 담아서 풀어버리려고 시도를 했다.

 

2. while문으로  done 값을 체크해서 끝내는 방식을 for문으로 그저  jobs.length 만큼 작업하고 끝내려했다.

예외케이스 존재  작업 후  다음 작업까지 텀이 있는 경우.   재반복을 해야하기에  for로 ++ 늘리지 않고 while로 작업이 완료 된 후 done++ 로 늘려주는 작업!

 

3. 큐 두개를 사용하는게 다소 생소했다.  (일반큐 , 우선순위 큐 )

기존껀 반복을 위한 큐  -> 그리고 조건에 맞는 작업을 하기 위한 우선순위큐 두 가지를 사용하는게 다소 어렵고 신기했다.

기본큐에서 시작시간 기준 오름차순으로 넣어주고, 거기서 꺼내서 이제 조건(작업 후 시작시간이 이미 도달한  다음 작업들)에 맞는 큐들은  우선순위 큐에 옮겨주기 -> 그리고 그 우선순위큐에서 하나씩 꺼내 최종 작업 연산.