211115 - 배상 비용 최소화

이상해씨·2021년 11월 15일

알고리즘 풀이

목록 보기

9/94

◾ 배상 비용 최소화 : 프로그래머스 LEVEL 2

문제

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. 해설

남은 값의 제곱의 합을 구하므로 각각의 남은 작업량의 값이 작아져야한다.
작업 기간만큼 해당 순서에서의 최대 작업량을 가지는 작업을 1만큼 수행하여 남은 작업량을 가능한 최소로 만들어 준다.
매번 최대값이 변경될 수 있으므로 최대힙 구조를 사용한다.

2. 프로그램

works를 최대힙 heap으로 재구성
작업 기간 no만큼 반복
- 최대 작업량을 뽑아 -1 수행
- 수행 결과를 heap에 다시 push
- 만약 수행 결과가 음수일 시 0 반환
  - 수행 결과가 음수이면 뽑은 값이 0으로 모든 작업이 수행된 것을 의미
heap의 모든 값을 제곱하여 더한 결과 반환

# 코드
'''
배상 비용은 남은 작업량의 제곱의 합이기 때문에
작업 기간이 가장 길게 남은 일부터 하루씩 작업 기간을 줄여야한다.
작업 기간을 줄이다 보면 최대값이 변하기 때문에 최대힙을 사용한다.
'''
import heapq
def solution(no, works):
    result = 0  # 결과
    heap = []   # 최대힙

    # 최대힙 heap을 구성하기 위해 (-value, value)의 쌍으로 추가
    # heapq는 최소힙으로 구성되기 때문에 이와 같은 방법으로 구성
    for work in works:
        heapq.heappush(heap, (-work, work))
    
    # 가장 기간이 길게 남은 작업부터 진행
    # 1일의 작업을 진행하고 다시 heap에 추가
    for i in range(no):
        # 현재 가장 많이 남은 작업량을 1만큼 처리
        work = heapq.heappop(heap)[1] - 1
        # 최대힙이므로 음수가 나오는 경우 모든 작업을 처리했다는 의미
        # 따라서 0을 반환
        if work < 0:
            return 0
        heapq.heappush(heap, (-work, work))

    # 남은 작업량의 배상 비용 계산
    # 0이 나올 경우 남은 값이 0밖에 없으므로 반복 종료
    while heap:
        work = heapq.heappop(heap)[1]
        if work == 0:
            break
        result += work ** 2

    return result