Level 3 야근지수 Python3

https://programmers.co.kr/learn/courses/30/lessons/12927?language=python3 

코딩테스트 연습 - 야근 지수

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_야근지수.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from heapq import heappop, heappush
def solution(n, works):
    if sum(works)-n <= 0: return 0
    max_heap = []
    for w in works:
        heappush(max_heap, (-w, w))
    while n > 0:
        root = heappop(max_heap)[1] - 1
        heappush(max_heap, (-root, root))
        n-=1
    return sum([w[1]**2 for w in max_heap])

---

풀이 과정

from heapq import heappop, heappush
def solution(n, works):
	#전체 작업량보다 남은 시간이 크거나 같은 경우, 모든 작업을 할 수 있다
    if sum(works)-n <= 0: return 0
    max_heap = []
    for w in works:
        heappush(max_heap, (-w, w))
    while n > 0:
    	#가장 작업량이 큰 일을 작업한다
        root = heappop(max_heap)[1] - 1
        #남은 작업량을 다시 힙에 넣어준다
        heappush(max_heap, (-root, root))
        n-=1
    return sum([w[1]**2 for w in max_heap])
#시간복잡도 = O(nlogn), 공간복잡도 = O(n)