[프로그래머스] 야근지수

문제

 

풀이

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        PriorityQueue<Integer> pqWorks = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        int sum = 0;
        for (int work : works) {
            sum += work;
            pqWorks.offer(work);
        }
        
        if (n > sum) return answer;
        
        while (n > 0) {
            Integer maxWork = pqWorks.poll();
            n--;
            pqWorks.offer(maxWork - 1);
        }
        
        
        answer = getOvertimeWorkingRate(pqWorks.toArray(new Integer[0]));
        
        return answer;
    }
    
    public long getOvertimeWorkingRate(Integer[] remainWorks) {
        long rate = 0;
        for (int remainWork : remainWorks) {
            rate += remainWork * remainWork;
        }
        return rate;
    }
}

• 가장 많이 남은 일부터 1씩 뺀다.
• 이걸 array로 for문 돌려서 가장 큰 일을 찾아 -1씩 하니 효율성 시간초과.
• 우선순위큐로 구현하니 시간초과 안난다.

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