[코딩테스트] 프로그래머스 - 야근 지수

1. 아이디어 

▪ 일의 작업량 리스트를 최대 heap에 넣기

▪ n이 0일 때까지 while문 반복

   - 최대 heap에서 일의 작업량 중 가장 큰 값 꺼내기

   - 꺼낸 작업량에 -1하고 다시 최대 heap에 넣기

   - n -= 1

▪ 남은 작업량의 제곱합 구해서 야근 지수 구하기

2. 시간복잡도

▪ O(nlogm),  m = works의 길이

3. 변수

▪ 최대힙: heap

Code

import heapq

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

 

프로그래머스