[프로그래머스] Lv3. 야근 지수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

코드

from collections import deque
import heapq
def solution(n, works):
    if n >= sum(works):
        return 0
    works = [-x for x in works]
    heapq.heapify(works)
    for _ in range(n):
        tmp = heapq.heappop(works)
        
        tmp += 1
        heapq.heappush(works, tmp)
    return sum([i ** 2 for i in works])

 

풀이

• 제곱의 합을 줄이려면 가장 큰 값을 줄여나가는 것이 좋다.
• 정렬을 이용해서 구하는 것보다, 최대힙을 만들어서 항상 최대값을 꺼내오는게 효율성이 높다.