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

문제

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

실패 코드

def solution(n, works):
    answer = 0
    works.sort(reverse = True)
    
    for i in range(n):
        if sum(works) == 0:
            return 0
        works[0] = works[0] - 1
        works.sort(reverse = True)
    
    for i in works:
        answer += i**2
    
    return answer

• 정확성은 100점인데 효율성 0점!!!!!!!!
• sort()는 O(nlogn)인데 매번 sort -> 최악의 경우 O(n*nlong) ㅎㅎ,,

정답 코드

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

• 남은 작업량 없을 때 0으로 return 하는거 젤 앞으로 빼줌
• heapq 라이브러리 사용
• heapq는 기본적으로 min heap의 형태이지만, 모든 원소의 부호를 바꿔주면 max heap과 비슷하게 사용할 수 있다. 연산 부호도 반대로 적용하기!!

참고

우선순위큐