[Programmers]Python_야근 지수

문제

문제 설명

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

제한사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

코드

import heapq
def solution(n, works):
    #작업량보다 작업시간이 크거나 같으면 모든 작업량을 처리할 수 있는 것이므로 0 return
    if sum(works) <= n:
        return 0
        
    #가장 큰 값을 가장 작은 값으로 만듬
    works = list(map(lambda x: x * -1, works))
    #가장 작은 값이 최상위 노드가 됨
    heapq.heapify(works)
    
    #작업량이 제일 큰 것을 첫 번째 우선순위로 n만큼 차례대로 빼주면 야근 피로도를 최소화할 수 있다
    for i in range(n):
        #이전에 음수 값으로 변경해주었으므로 +1을 하여 줄여준다
        cur_work = heapq.heappop(works) + 1
        #작업량이 이미 없다면 pass
        if cur_work >= 0:
            continue
        #줄어든 작업량을 다시 추가한다
        heapq.heappush(works, cur_work)
    
    return sum(map(lambda x: x ** 2, works)) #야근 피로도 계산

 

진행 과정

예제 #1

works = [4, 3, 3]

n = 4

 

1) works = [-4, -3, -3] #-1을 곱해줌으로서 가장 높은 작업량을 가장 작은 작업량으로 변경
2) works = [-4, -3, -3] #heapify()를 사용하여 -4 -> -3 -> -3 순으로 -4가 최상위 노드
3) works = [-3, -3, -3] #-4 + 1 = -3
4) works = [-3, -3, -2] #-3 + 1 = -2 (heappush로 추가해줌으로서 -2값이 leaf값으로 넘어감)
5) works = [-3, -2, -2] #-3 + 1 = -2 
6) works = [-2, -2, -2] #-3 + 1 = -2 

 

7) return 12 (모두 제곱한 값을 더한 값)