[Programmaers][Lv.3] 야근지수

[문제 링크] - https://programmers.co.kr/learn/courses/30/lessons/12927


문제 설명

제한사항

풀이

def solution(n, works):
    if sum(works) <= n: return 0 
    works.sort(reverse=True)
    while n != 0:
        diff = works[0] - works[1]
        if diff == 0:		    #최고값 원소들이 여러개 일 때
            cnt = works.count(works[0]) 
            
            for i in range(cnt):    # 최고값 원소들 값 감소
                works[i] -= 1
                n -= 1
                if n <= 0:
                    break
            works.sort(reverse=True)
            
        elif n > diff:		
            works[0] -= diff
            n -= diff
        else:
            works[0] -= n
            n = 0

    answer = sum(list(map(lambda x: x*x, works)))
    return answer

야근 피로도는 각 원소들의 제곱으로 계산되므로 최소화를 위해서는 최대값 원소를 감소시키는것이 관건이다.

우선 남은 업무보다 시간이 클 경우 0을 반환하였다.

이외의 경우 최대값을 차례차례 감소시키기 위해 내림차순으로 정렬을 하였다.
n이 0이 될때 까지 감소시키며 반복을 실시하고 첫 번째 원소(최대값)와 두 번째 원소(2번째로 큰 값)를 계산한다.

1. 차이가 0일경우 최고값 원소들이 여러개 있다는 뜻이다.
   한번에 감소시키기 위해 내부에서 갯수만큼 반복을 실시하여 값을 감소시킨다.
   중간에 n을 다 소모하면 바로 반복문을 탈출하도록 한다.
   그리고 최고값이 감소하였으므로 다시 정렬을 해준다.

2. 차이가 0이 아니고 n보다는 작을 경우, 차이만큼 첫 번째 원소를 감소시킨다.
   소모된 만큼 n에도 반영한다.
   여기에서는 두 번째 원소와 같아지므로 다시 정렬할 필요가 없다.

3. 마지막으로 차이가 0이 아니고 n보다 클 경우,
   첫 번째 원소를 남은 n만큼 감소시키고 n을 0으로 만든다.
   n이 0이되었으므로 마지막 반복이라는 뜻이다. 즉 다시 정렬할 필요가 없다.

n을 모두 소모했으면 각 원소들의 제곱합을 계산하여 반환한다.

결과

추가

import heapq

def solution(n, works):
    answer = 0
    if sum(works) <= n:
        return 0
    queue = list()

    for i in works:
        heapq.heappush(queue,i*(-1))
        
    for _ in range(n):
        temp = heapq.heappop(queue)
        heapq.heappush(queue,temp+1)
    
    answer = sum(list(map(lambda x: x*x, queue)))
    return answer

나는 억지로 반복을 통해 풀었지만... 다른분들의 풀이를 보니 heap을 이용하여 매우 쉽게 풀어낸 것을 볼 수 있었다.....

시간복잡도가 낮은 힙을 이용하여 최대값에서 계속 1을 감소시키는 방향으로...

-1을 곱해서 넣는 이유는 파이썬의 heapq 모듈은 기본적으로 min heap이기때문이다.