[프로그래머스] (파이썬)배상비용최소화-Level2-힙(heap) 자료구조

안녕하세요. 진또배기입니다. 오늘은 파이썬을 사용해 프로그래머스에 올라와있는 '배상비용최소화'문제를 풀어보도록 하겠습니다.

1. 문제 설명

문제 설명

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

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

제한사항

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

---

2. 슈도코드

슈도코드를 작성하기 전에 어떻게 해야 배상비용을 최소화 할 수 있을까에 대해 고민해봅시다. 
배상비용을 최소화하려면 가장 작은 작업량을 낮추는 것보다 가장 큰 작업량을 낮추는 것이 중요합니다. 
그 이유는 다음 식으로 일반화 해보겠습니다.

1) works배열에서 가장 큰 작업량을 찾는다. 
2) 찾은 작업량을 -1 해준다.
3) 위 과정을 no번 반복해준다.
4) 반복이 끝나면 각 작업량의 제곱의 합을 반환한다.

5) 단, 작업량이 작업시간보다 작거나 같다면 0을 반환한다.

---

3. 문제 풀이

0) if 작업량 <=작업시간 이라면 0을 반환  (즉, 잔여 작업량을 모두 끝내는데 시간이 충분하다면 0을 반환)
1) 가장 큰 작업량을 빠르게 찾을 수 있는 자료구조(힙)를 사용해 가장 큰 작업량을 찾는다.
2) 가장 큰 작업량을 -1 해준다.
3) for _ in range(no)번 반복해준다.
4) return sum(원소 ** 2 for 원소in 잔여작업량 자료구조)   -->각 작업량의 제곱의 합

---

4. 알아야할 스킬셋

사용하면 좋은 스킬들이 두 가지가 있습니다. 첫 번째로 힙자료구조입니다. 힙은 1. 데이터의 삽입/삭제가 빈번하고, 2. 정렬을 유지해야 할 때 유용한 자료구조입니다.
비전공자입장에서 저는 list를 쓰고 list.sort()로 정렬 한 뒤 가장 큰 수 인 list[-1]을 해주면 되지 않을까? 라고 생각했습니다.                                                            =[3,1,2]         =[1,2,3]                                         =3
하지만 list를 쓰게되면 시간복잡도가 O(n)이고 힙을 사용하면 O(nlogn)이기 때문에 더 효율적입니다.

두 번째는 

sum(work ** 2 for work in max_heap)

와 같은 LC입니다. List comprehension은 리스트를 쉽게 생성하기 위한 방법입니다. 

다양한 예시를 들어보며 이해를 돕겠습니다. 

1) 20까지의 짝수를 출력하기 위해 다음과 같은 LC를 사용할 수 있습니다
evens = [x * 2 for x in range(11)]
# [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

2) 리스트의 모든 원소값을 정규화 시킨 후 상수값을 더하는 LC
vals = [32, 12, 96, 42, 32, 93, 31, 23, 65, 43, 76]
amount = sum(vals)
norm_and_move = [(x / amount) + 1 for x in vals]
# [1.0587155963302752, 1.0220183486238532, 1.1761467889908257, 1.0770642201834861, 1.0587155963302752]

이것은 파이썬에서 보편적으로 사용되는 기능으로 조금만 응용하면 다양한 조건으로 리스트를 생성할 수 있는 강력한 기능중 하나입니다.

---

5. 문제 풀이를 하며 든 생각

비전공자분들을 위해 제가 힙자료구조를 모른다고 생각하고 문제를 풀어보았습니다.

이 코드도 실행은 되지만 for문 두개를 사용해 시간복잡도가 O(nm)이기때문에 효율성을 통과하지 못합니다.
n은 no의 크기, m은 works의 크기

하지만 힙을 사용하면 O(nlogm)이기 때문에 더 빠르게 계산한다는 것을 알 수 있습니다.
n은 no의 크기. logm은 힙자료구조 안에 들어간 works의 크기

사실 이 문제를 보았을 때, 힙 자료구조를 떠올리기 쉽지 않습니다.

그렇다면 힙자료구조가 쓰이지 않는 문제에 대해서 언급하자면 데이터를 정렬하고 정렬한 순서대로 순회만 할때, 사용하지 않습니다.

따라서 많은 문제를 풀어보아야하며 힙은 위에 언급한것처럼 1. 데이터의 삽입/삭제가 빈번하거나, 2. 빈번한 정렬을 유지해야 할 때 사용합니다.

오늘은 파이썬을 사용해 프로그래머스의 '배상비용 최소화'문제를 풀어보았습니다.

진또배기 올림