문제

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

---

입력

퇴근까지 남은 N 시간과 각 일에 대한 작업량 works

---

출력

야근 피로도를 최소화한 값

---

풀이

제한조건

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

접근방법

문제를 살펴보면 구하고자하는 값이 남은 works의 값들을 제곱해서 더한 것이므로,
최대한 균일하게 낮을 수록 최소값을 구할 수 있다.
단순하게 접근하자.

힙을 사용하면 가장 단순하다.
(힙을 모른다면? : https://velog.io/@hyeokkr/HeapMaxMin)
힙으로 구성된 우선순위큐를 이용해 풀어보자.

문제 접근 방식은 아래와 같다.

1. 우선순위 큐에 큰 수가 먼저 나오도록 집어넣는다.
2. N이 0보다 크다면, 원소 하나를 꺼낸다.
3. 원소의 값과 N의 값을 1씩 감소시킨다.
	그 후 원소의 값이 0보다 크다면 다시 큐에 넣는다.
4. 큐가 비거나, N이 0이 될때까지 반복한다.
5. 큐의 모든 원소를 꺼내며 제곱해서 더한다.

위 과정을 통해 큰 수부터 1씩 감소시킬 수 있고, 제곱하는 과정에서 밑이 최대한 작게 만들어지며 야근 피로도를 최소화 할 수 있다.

프로그래머스 Lv3 문제 중 가장 쉬운것 같다.

---

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
    	// 큰 수가 우선순위가 높은 큐를 선언.
        PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
        
        // works의 모든 원소를 큐에 넣는다.
        for(int i : works)
            pq.add(i);
        
        // 반복 로직 수행
        while(true){
            if(n==0)
                break;
            if(pq.isEmpty())
                break;
            int value = pq.poll();
            n--;
            value -= 1;
            if(value >0)
                pq.add(value);
        }
        
        long answer = 0;
        // 큐의 모든 원소를 꺼내며 계산한다.
        while(!pq.isEmpty()){
            int value = pq.poll();
            answer += value * value;
        }
        return answer;
    }
}