[level 2] 배상 비용 최소화

문제 설명

OO 조선소에서는 태풍으로 인한 작업지연으로 수주한 선박들을 기한 내에 완성하지 못할 것이 예상됩니다. 기한 내에 완성하지 못하면 손해 배상을 해야 하므로 남은 일의 작업량을 숫자로 매기고 배상비용을 최소화하는 방법을 찾으려고 합니다.
배상 비용은 각 선박의 완성까지 남은 일의 작업량을 제곱하여 모두 더한 값이 됩니다.
조선소에서는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 조선소에서 작업할 수 있는 N 시간과 각 일에 대한 작업량이 담긴 배열(works)이 있을 때 배상 비용을 최소화한 결과를 반환하는 함수를 만들어 주세요. 예를 들어, N=4일 때, 선박별로 남은 일의 작업량이 works = [4, 3, 3]이라면 배상 비용을 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 배상 비용은 22 + 22 + 22 = 12가 되어 12를 반환해 줍니다.

제한사항

일할 수 있는 시간 N : 1,000,000 이하의 자연수
배열 works의 크기 : 1,000 이하의 자연수
각 일에 대한 작업량 : 1,000 이하의 자연수

입출력 예

N	works	result
4	[4,3,3]	12
2	[3,3,3]	17

---

코드

import heapq
def solution(no, works):
    if no >= sum(works):
        return 0
    tmp = list()
    for item in works:
        heapq.heappush(tmp, (-item,item))
    
    for _ in range(no):
        num = heapq.heappop(tmp)
        heapq.heappush(tmp, (-(num[1]-1), num[1]-1))
    
    return sum([x[0]**2 for x in tmp])

배운 점

전에 분명히 풀어본 것 같은데...깃헙을 뒤져도 안보여서 띠용했던 문제
문제 자체는 어렵지 않으나 효율성을 통과하는게 까다로웠다.
no의 크기만큼 횟수를 세면서 works 중 값이 가장 큰 원소를 -1씩 시켜주면 되는 문제
그런데 그냥 for문을 돌면서 sort를 사용할 경우 효율성을 통과할 수 없었다.
그래서 heapq를 사용해서 효율성을 통과했다.
먼저 heapq는 minheap의 구조를 갖고 있기 때문에 maxheap으로 구조를 바꿔줘야했다.
다른 방식이 분명히 있을 것 같은데 간단하게 (-item, item)을 넣는 방식으로 구성했다.
그 후에 heappop을 하고 -1을 하고 다시 push 해준 뒤 제곱값을 더해준 뒤 return 해줬다.