[프로그래머스] 배상 비용 최소화

문제 설명

OO 조선소에서는 태풍으로 인한 작업지연으로 수주한 선박들을 기한 내에 완성하지 못할 것이 예상됩니다. 기한 내에 완성하지 못하면 손해 배상을 해야 하므로 남은 일의 작업량을 숫자로 매기고 배상비용을 최소화하는 방법을 찾으려고 합니다.
배상 비용은 각 선박의 완성까지 남은 일의 작업량을 제곱하여 모두 더한 값이 됩니다.

조선소에서는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 조선소에서 작업할 수 있는 N 시간과 각 일에 대한 작업량이 담긴 배열(works)이 있을 때 배상 비용을 최소화한 결과를 반환하는 함수를 만들어 주세요. 예를 들어, N=4일 때, 선박별로 남은 일의 작업량이 works = [4, 3, 3]이라면 배상 비용을 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 배상 비용은 22 + 22 + 22 = 12가 되어 12를 반환해 줍니다.

제한사항

• 일할 수 있는 시간 N : 1,000,000 이하의 자연수
• 배열 works의 크기 : 1,000 이하의 자연수
• 각 일에 대한 작업량 : 1,000 이하의 자연수

입출력 예

N	works	result
4	[4,3,3]	12
2	[3,3,3]	17

입출력 예 설명

입출력 예 #1

• 문제의 예제와 같습니다.

입출력 예 #2

• 배상 비용을 최소화하기 위해 일을 한 결과는 [2, 2, 3]가 되고 배상 비용은 22 + 22 + 32 = 17가 되어 17를 반환해 줍니다.

풀이

• 최소 힙을 최대 힙으로 변형한 코드
• 힙의 경우 부모의 값이 항상 자식보다 작은 완전 이진 트리임
  • 힙의 경우 값이 삽입되거나 삭제되는 경우에도 아래와 같이 우선순위가 유지되는 특징이 있음

• 배상 비용을 최소화하기 위해서는 남은 모든 일들중에 큰 놈이 없어야하므로, 가장 큰 값을 추출해서 하나씩 제거. 이때, 가장 큰 값을 계속해서 추출하기 위해 힙을 이용
  • heapq의 값이 작은 것을 우선순위가 높다고 해서 작은 값부터 나오지만, 튜플을 이용해서 우선 순위에 -를 붙여서 큰 값을 우선순위가 높게 바꿀 수 있음 works = [(-i, i) for i in works]
  • 이후, 리스트를 힙으로 변경 heapq.heapify(works)
• 우선순위가 높은 작업을 꺼내서 1을 뺀 후에 다시 힙으로 삽입을 N번 반복
• 모든 작업에 대해 남은 작업량 계산 sum([i[1]**2 for i in works])

import heapq

def solution(N, works):
    if N > sum(works) :
        return 0
    # heap은 원래 최소 힙을 기준으로 하지만 -를 붙여서 최대 힙으로 변경이 가능 
    works = [(-i, i) for i in works]
    # 기존 리스트를 heap으로 변환하는 코드
    heapq.heapify(works)
    for _ in range(N) :
        # 가장 값이 큰 작업을 꺼내서 작업량 1을 수행 
        # [1]은 우선 순위에는 관심이 없으므로 값만 가져옴 
        w = heapq.heappop(works)[1] - 1
        # works에 수정된 w를 추가 
        heapq.heappush(works, (-w, w))
    return sum([i[1]**2 for i in works])

출처: 프로그래머스 코딩 테스트 연습,https://programmers.co.kr/learn/challenges