[프로그래머스 알고리즘 스터디] 1주차 - 배상 비용 최소화

YUZAMIN
YUZAMIN
Hello, World! I'm YUZAMIN, a diligently endeavoring frontend developer 🐤💦
[프로그래머스 알고리즘 스터디] 1주차 - 배상 비용 최소화

Summary

문제 설명 📑

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

문제 풀이 👩🏻‍💻

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 배상 비용 최소화
import heapq


def solution(n, works):
    # 만약 작업량의 합이 일할 수 있는 시간 n보다 작을 경우
    # 즉, 모든 일을 일할 수 있는 시간 내에 끝낼 수 있다면
    # 0을 return
    if n >= sum(works):
        return 0

    works_heap = []
    answer = 0

    # 작업량을 heap에 내림차순으로 삽입
    # 더 많은 작업량을 우선적으로 처리하기 위함
    for work in works:
        heapq.heappush(works_heap, (-work, work))

    # n이 다 소진될 때까지 반복
    while n > 0:
        # 가장 많이 남은 작업의 작업량을 꺼내서 1을 빼고
        # n에서도 1을 빼기 = 1시간을 소모하여 해당 작업 수행함
        n -= 1
        work = heapq.heappop(works_heap)[1] - 1

        # 1을 빼준 해당 작업을 다시 내림차순으로 heap에 삽입
        heapq.heappush(works_heap, (-work, work))

    # heap에 남은 작업량들을 제곱하여 answer에 할당
    for work in works_heap:
        answer += work[1] ** 2

    return answer

문제 출처