(코테) 프로그래머스_야근 지수 *우선순위 큐

 

 

문제 링크

 

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

 

 

 

수정전

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        //야근 시작시점. 
        // 야근피로도 =  야근 시작시점 + 남은 작업의 제곱 ^2
        
        // N시간동안 야근 피로도를 최소화하도록 일함.
        // 시간당 1 처리 가능 
        // 작업량 works        
        // n
        // 5-1  4/3
        // 10 -4=6 
        // 2 2 2 
        
        int len = works.length;
        
        int sum= 0;
        
        for(int next:works) sum += next;            
        if(sum<=n) return 0;
        sum = sum-n;
        
        int avg = sum/len;
        int etc = sum%len;
        
        // ex) 몫=1  나머지=1
        // 4가 최소값   3개 모자람 
            int doubleAvg=(avg * avg);            
        if(etc==0){            
           answer += doubleAvg * len;
        }else{
           int doubleAvg2=((avg+1) * (avg+1));
            for(int i=0;i<len;i++){                
                if(i<etc){
                  answer += doubleAvg2;
                  continue;
                }                
                answer += doubleAvg;
            }
        }     
 
        return answer;
    }
}

 

 

 

 

 

수정후

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        //야근 시작시점. 
        // 야근피로도 =  야근 시작시점 + 남은 작업의 제곱 ^2
        
        // N시간동안 야근 피로도를 최소화하도록 일함.
        // 시간당 1 처리 가능 
        // 작업량 works        
        // n
        // 5-1  4/3
        // 10 -4=6 
        // 2 2 2 
            
        PriorityQueue<Integer> q = new  PriorityQueue<>(Comparator.reverseOrder());
        int sum=0;
        for(int next:works){
          sum += next;            
          q.offer(next);
        } 
        if(sum<=n) return 0;
        
        
        while(n>0){
            n--;
            int cur =q.poll();
            if(cur==0) break;                                                
            q.offer(cur-1);            
        }
        
        long sum2 =0;
        
        for(int next:q) sum2 += (long) next * next;            
                
 
        return sum2;
    }
}