야근 지수

📖 연습문제 > 야근 지수

📖What I thought

• 처음엔 최댓값을 n만큼 -1 하면 되는거 아닌가(-1해서 최댓값 바뀌면 해당 최댓값을 == 즉 최대한 숫자를 비스무리하게 ) 생각했는데 이 때는 우선순위큐 생각 못해서 계속 정렬해야한다고 생각하고 시간이 너무 많이 걸릴 거 같아서 포기
• 그러고 그냥 잔여량 다 더해서 n만큼 빼고 균등분배 후 나머지만큼의 원소에다가 (나머지가2라면 2개의 원소) +1 해줌 → 단단히 잘못되었던 생각.. 만약 [9, 1]이고 n이 1이면 65여야하는데 이건 41이 나옴;; 바보!!!!!!
• 그래서 그냥 첫번째 안으로 다시 돌아가서 heapq는 복잡도가 log n이니까 이걸 이용해서풀었음!

📖풀이

📎heapq

import heapq
 
def solution(n, works):
    works = [-w for w in works]
    
    heapq.heapify(works)
    for _ in range(n):
        heapq.heapreplace(works, works[0]+1)
    
    tired = 0
    for w in works:
        if w >= 0:
            continue
        
        tired += w*w
 
    return tired

📖What I learned

• 파이썬의 heapq는 값이 변할 땐 재정렬이 되지 않고 push, pop, replace 같은 함수 연산이 발생할 때만 정렬이 되어 최솟값이 고정됨!
• heapq로 pop → push한다면 heapq.replace(list, v) 라는 함수가 있음!

📖관련 지식

📎Heapq