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

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

프로그래머스

 

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        //works를 우선순위 큐에 넣자
        for(int i=0;i<works.length;i++){
            pq.add(works[i]);
        }
        
        while( n>0 && !pq.isEmpty()){
            int tmp = pq.poll();
            if(tmp != 1) pq.add(tmp-1); //제일 큰 값에서 1을 빼고 다시 넣어준다.
            n--;
        }
        
        while(!pq.isEmpty()){
            int tmp = pq.poll();
            answer = answer + (tmp * tmp);
        }
        return answer;
    }
}

 

우선순위 큐 내림차순 정렬을 꼭 기억해두자 !

1. 우선순위 큐에 작업 넣고

2. 제일 큰 값 부터 줄여간다. ( 남은 작업량의 제곱의 합이 야근지수이기 때문에 큰 수를 줄여야 야근지수가 작아질 수 있다)

3. n만큼 반복

4. 남은 작업량이 1이면 이번 차례에 작업을 마치는 것이므로, 큐에 넣지 않는다.

5. 반복이 완료되면 큐에 있는 것들 꺼내서 제곱해서 더해주면 끝