[우선순위 큐] 야근 지수 ***

문제 설명

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

프로그래머스

문제 풀이

• 큰 값을 모두 처리하는 것보다 큰 값들을 모두 균등하게 처리해야 제곱값들의 합이 최소가 나옴
• a^2 + b^2 <(a+b)^2 이기 때문(?)
• works에서의 최댓값을 항상 균등하게 맞춰가면서 -1 해야하므로 최댓값을 계속해서 뽑아줘야함
• 이를 정렬로 구현할 시 works는 최대 길이가 n*20,000*log(20,000) 이 발생. (works<=20,000 , n<=1,000,000)
• 대체안으로 항상 큰 값을 pop 해주는 최대 힙 우선순위 큐를 사용 (삽입,삭제 log(n))

소스 코드

import heapq

def solution(n, works):
    if(sum(works)<=n):
        return 0
    answer = 0
    q = []
    for i in range(len(works)): 
        heapq.heappush(q,(-works[i]))	#최대 힙을 사용할거라 음수값으로 넣어줌
    while(n!=0):
        max_n = heapq.heappop(q)*(-1)
        max_n-=1
        n-=1
        heapq.heappush(q,(-max_n))
    for i in range(len(q)):
        answer+=q[i]**2
    return answer

    
print(solution(4,[4,3,3]))