[프로그래머스/Python] 야근 지수

문제

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

프로그래머스

 

n시간 야근 하는 동안 야근 지수를 최소화하여 야근 지수 제곱을 리턴

---

 

n시간 안에 작업량을 다 끝내면(작업량 합이 n보다 작거나 같으면) 0을 리턴

sum(works) <= n

 

제곱을 해서 더하기 때문에 큰 값을 줄여야 한다

 

1. 

def solution(n, works):
    answer = 0
    if sum(works) <= n:
        return 0
    for _ in range(n):
        works[works.index(max(works))] -= 1
    return sum([w*w for w in works])

 

 

효율성 테스트 보완

2. heapq 사용

import heapq
def solution(n, works):    
    if sum(works) <= n:
        return 0
    
    works = [-w for w in works]
    heapq.heapify(works)
    
    for _ in range(n):
        w = heapq.heappop(works)
        heapq.heappush(works, w+1)
    return sum([w*w for w in works])

heapq는 최소힙 기준

[1, 2, 3, 4, 5] 정렬

최소힙: 1 <  2 < 3 < 4 < 5

최소힙: -5 < -4 < -3 < -2 < -1