[Python] 프로그래머스 Lv 3 - 야근 지수

프로그래머스 Lv 3 - 야근지수 풀이

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

 

알고리즘

제곱의 특성 상, 큰 값을 더 크게 만드므로, 남은 N시간 동안, 가장 작업량이 많은 거를 1개씩 줄여 나가면 될 것이다.

즉, 계속 최댓값을 찾아줘야 하는 문제이다.

 

이에 적합한 자료구조는  최대와 최소를 간편하게 찾아주는 heap 자료구조이다.
다행히, Python에는 heapq 형태로 자료구조가 이미 구현되어 있다.

허나, 문제는 heapq는 Min Heap을 기반으로 하고 있다. 이를 Max로 바꾸려면 어떻게 해야 하나.?

자료구조를 Max로 바꿀 생각을 하지 말고, 주어진 배열이 모두 양수이므로, -1을 곱해서 모두 음수로 만들면  Min Heap을 그대로 사용해도 문제가 없다.!

(단, 이렇게 할 경우 문제에서 말하는 것과 양음이 바뀌어서 모든 부호를 반대로 구현해야 한다. 이를 주의해야 한다)

 

코드

import heapq
def solution(n, works):
    answer = 0
    works = [-x for x in works]
    heapq.heapify(works)
    
    while n > 0:
        work = heapq.heappop(works)
        work += 1
        heapq.heappush(works, work)
        n -= 1
    
    if works[1] > 0:
        answer = 0
    else:
        for i in works:
            answer += (i ** 2)

    return answer