[프로그래머스] level3 - 야근지수 파이썬 풀이

 

풀이 시간 : 15분

level3 맞나,,,?

 

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

프로그래머스

 

 

 

 

핵심

최대 일들 부터 처리해줘야 제곱의 합이 작아진다.

 

접근법

1. 정렬 (문제는 맞으나 매번 for 문마다 정렬하면 효율성이 떨어진다)

2. heap (자동으로 정렬되는 heap 이용)

 

 

 

heap 이용한 풀이

import heapq

def solution(n, works):
    heap = []
    #최대 힙으로 만든다
    for work in works:
        heapq.heappush(heap, (-work,work))
    
    #최대 값부터 하나씩 일을 처리한다
    for i in range(n):
        max_ = heapq.heappop(heap)[1]
        #일을 처리하고 난 뒤 다시 heap 에 넣고 정렬
        heapq.heappush(heap, (-1*(max_-1), max_-1))
    
    # 일하고 난 뒤 값들만 다시 work로 변환
    works = [i[1] for i in heap]
    
    # 일할 수 있는 시간이 일량보다 많을 때
    if sum(works) < 0:
        return 0
    else:
        return sum([w**2 for w in works])

 

heapq 만 이용할 줄 알면 level3 답지 않게 15분이면 풀기 가능... (15분인 이유는 정렬로 먼저 풀었다가 heap으로 다시 풀었기 때문)