[Algorithm] [Python] Programmers - 배상 비용 최소화

Programmers - 배상 비용 최소화

 

문제 설명

---

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 이하의 자연수

 

입출력 예

---

제출 코드

---

import heapq

def solution(no, works):
    MaxHeap = []

    if no >= sum(works):
        return 0

    for work in works:
        heapq.heappush(MaxHeap, (-work, work))

    for _ in range(no):
        work = heapq.heappop(maxHeap)[1] - 1
        heapq.heappush(MaxHeap, (-work ,work))

    return sum(i[1] ** 2 for i in MaxHeap])

 

문제 풀이

---

문제의 핵심은 Heap 자료구조다.

다만, 파이썬의 heapq 모듈은 MinHeap을 기반으로 구현되었기에 이를 응용하여 MaxHeap을 사용한다.

(-value, value) 로 원소를 지정하여 (우선순위, 실제 값)으로 사용한다.

works 배열을 MaxHeap 으로 변환한 뒤, no 만큼 순회하며 최대값을 뽑아내어 -1 연산을 진행한다.

이후 MaxHeap의 모든 원소의 1번째 원소를 뽑아내어 해당 값의 제곱값을 모두 더하여 반환한다.