📌 프로그래머스 - 야근 지수

최대값을 찾아 최대값을 하나씩 감소 시켜줌으로써 쉽게 풀 수 있는 문제!
우선순위큐만 알고 있으면 쉽게 풀 수 있다.

나는 heapq를 최대 힙으로 구현해서 풀었다!

📝 내 답안

from heapq import heappush,heappop,heapify
def solution(n, works):
    answer = 0
    
    if sum(works) <= n:
        return 0
    
    w = [-i for i in works]
    heapify(w)
    
    for _ in range(n):
        m = heappop(w)
        m += 1
        heappush(w,m)
    
    while w:
        answer += heappop(w)**2
    
    return answer

🔮 설명

이 문제는 최대 값에서 하나씩 감소시키면 쉽게 풀리는 문제지만, 어떻게 해야 저비용의 알고리즘을 구현할지 생각해봐야했다.(= 효율성 통과를 위해)

최대 값만 그 때 그 때 구해주고 -1해주고 다시 넣고, 최대 값 구하고.. 를 반복해야하기 때문에 우선순위 큐를 사용해야겠다고 생각했다.

일반 리스트는 삽입과 삭제가 O(N)인데 heap은 시간복잡도가 O(logN)에 불과하기 때문에 좋은 성능을 보여준다.!
((heappush() heappop() 은 시간복잡도 O(logN)))

본 문제의 경우 최대 값을 탐색하기 위해서는 모든 배열을 탐색해야하기 때문에, 리스트를 사용하면 시간초과가 뜬다.

heap은 자바의 우선순위큐(Priority Queue)와 같다.

최소값을 우선순위로 하는 큐로, 약간의 트릭을 사용하면 최대힙으로 활용 가능하다.

내가 활용하는 최대힙 구현 방법은 위 답안처럼 모든 값이 - 넣어 사용하는 것이다.

from heapq import heappush,heappop,heapify
def solution(n, works):
    answer = 0
    
    # 남은 일이 남은 시간 n보다 작으면 야근지수 0 반환
    if sum(works) <= n:
        return 0
    
    # w라는 리스트에 works의 원소들을 모두 음수로 바꾸어 저장(최대힙 구현을 위해)
    w = [-i for i in works]
    # w 리스트를 heapq로 변환
    heapify(w)
    
    # n번 반복하며 최대 값을 -1
    for _ in range(n):
        m = heappop(w)
        # 현재 모든 원소가 음수이므로 값을 차감하려면 +1
        m += 1
        heappush(w,m)
    
    while w:
        answer += heappop(w)**2
    
    return answer