야근 지수

프로그래머스

• 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다.
• Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.
• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

입출력

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

---

접근 방식

: works를 내림차순 정렬시켜서 n만큼 각각 1씩 빼주고 야근지수를 구한다. -> 틀렸습니다.

알게된 점

[8,3,3], n=4일 때 [6,2,2]보다 [4,3,3]가 더 적음. 즉 최대힙을 사용해서 가장 큰 수를 뽑아 1씩 빼줘야한다.

코드

import heapq
def solution(n, works):
    if sum(works) <= n:
        return 0
    
    #최댓값을 반복적으로 찾아내어 1씩 감소시킴
    works = [-x for x in works]
    heapq.heapify(works)
    
    for _ in range(n):
        x = heapq.heappop(works)
        heapq.heappush(works, x+1)
    
    return sum([x**2 for x in works])