[연습문제] 야근 지수 - JAVA

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

프로그래머스

---

흠 이 문제는 PriorityQueue의 효율성을 느낄 수 있었던 문제다ㅋㅋㅋㅋㅋ

이게 알고리즘 자체는 크게 어렵지 않은데, 효율성 통과가 관건이었던 것 같다

(물론 나는 정확성 테스트도 난리나긴 했다..^^)

 

암튼 우선순위 큐를 사용하라는 말을 듣고 고대로 풀어봤는데 쉽게 풀렸다!

조심할 것은 우선순위 큐를 역순으로 정렬하도록 선언해야 한다는거?

네... 제가 안했습니다..^^

 

그리고 반복문을 통해서 우선순위 큐에서 숫자를 꺼내가며 1씩 줄여주면 된다

왜냐? 제곱의 합이 작아지려면 각 숫자들이 최대한 작아져야 하기 때문이다!!!

그래서 그 때마다 배열의 최댓값을 n만큼 1씩 줄여주면 된다

 

여기서 또 주의할 점은!!

최댓값이 0이면 멈춰야한다는 것이다!

0이라는 것은 작업량이 없다는 것이니까!!

난 이거 안했다가 제곱의 합 구하는 거라 야근 지수가 엄청 높아졌다...^^

 

아무튼 각 예외 상황만 잘 고려해서 우선순위 큐로 풀면 쉽게 풀 수 있다!

 

 

 

자바 코드)

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int work : works) {
            pq.offer(work);
        }
        for(int i=0;i<n;i++) {
            int max = pq.poll();
            if(max<=0) {
                break;
            }
            pq.offer(max-1);
        }

        while(!pq.isEmpty()) {
            int p = pq.poll();
            answer += (p*p);
        }
        return answer;
    }
}