(파이썬) [알고리즘 문제 풀이] - 야근 지수 (프로그래머스)

문제 설명

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다.

야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. 

Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.

Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

풀이

n은 현재 남아 있는 일할수 있는 시간이며 이 시간을 활용하여 

works안에 있는 잔업마다 필요한 시간들을 줄여야 합니다.

n 시간을 모두 사용하고도 남은 잔업의 시간들은 각각 제곱한 후에 더 합니다.

그리고 이 값을 야근 피로도 라고 부릅니다.

즉, 야근 피로도를 줄이기 위해서는 숫자들의 제곱 값을 낮춰야 합니다.

제곱 값을 최대한 낮추기 위해서는 리스트 안에서 큰 숫자들부터 n을 사용하여 줄여야 합니다.

저는 이 부분을 해결하기 위해 리스트를 써서 지속적으로 max 함수를 쓴다면

시간 효율이 떨어질 것이라 판단했습니다.

그래서 Heap 구조를 쓰기로 결정 했습니다.

파이썬의 Heap은 가장 작은 숫자를 pop 하는 Minimum Heap이기 때문에

works 리스트 안의 숫자들에 마이너스를 곱하여서

Max Heap처럼 사용할수 있도록 했습니다.

 

코드

import heapq as hq

def solution(n, works):
    answer = 0
    works = [-x for x in works]		#리스트 안 숫자들을 음수로 변경
    hq.heapify(works)
    
    while n > 0:
        task = hq.heappop(works)
        if task == 0:
            return 0
        else:
            hq.heappush(works,task+1)
            n -= 1
        
    return sum([x**2 for x in works])

효율성 테스트가 따로 있는걸로 봐서는 만약 heap을 사용하지 않고 리스트를 사용해서 

loop을 돌때마다 max 함수를 불렀다면 시간 초과가 나왔을 것 같습니다.

파이썬의 heap 자료구조는 이렇게 계속적으로 최소값이나 최대값이 필요한 문제에서

반드시 필요한것 같습니다.