프로그래머스 Lv3_야근 지수_Java

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

프로그래머스

 

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // 오름차순
        
        for(int i : works) {
            pq.add(i);
        }
        
        while(n > 0 && !pq.isEmpty()) {
            int maxValue = pq.poll();
            maxValue -= 1;
            n -= 1;
            
            if(maxValue != 0) {
                pq.add(maxValue);
            }
        }
        
        while(!pq.isEmpty()) {
            int value = pq.poll();
            answer += (long) value * value;
        }
        
        return answer;
    }
}

 

 

풀이

- 우선순위 큐를 오름차순으로 사용하여 가장 많은 양의 일을 하나씩 빼내 1씩 감소시켜준다

- 감소시킨 일이 0이 아니면 다시 우선순위 큐에 넣어주고 0이면 넣지 않는다

- 반복 후 남은 일들을 하나씩 빼내서 제곱 후 모두 더하고 답을 도출했다

 

 

회고

- 풀이 방법만 떠오르면 그렇게 어렵진 않은 문제같다