문제 설명
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를 반환해 줍니다.
나의 풀이
첫번째 풀이
소스
from queue import PriorityQueue
def solution(no, works):
if no >= sum(works):
return 0
result = 0
priority_que = PriorityQueue()
# 최대값을 찾기 위해 priority를 음수로 바꿔준다.
for work in works:
priority_que.put((-work, work))
while no > 0:
after_max_work = priority_que.get()[1] - 1 # 최대 작업량을 가져와서 수행한다.
priority_que.put((-after_max_work, after_max_work)) # 다시 최대 우선순위 큐로 넣는다.
no -= 1
# 남은 작업량 의 배상 비용을 구한다.
for work_tuple in priority_que.queue:
result += work_tuple[1] ** 2
return result설명
이 문제는 list에 있는 수들이 평균과 비슷하고 가장 작게 형성이 되어 있어야 하는데 딱 봐도 heap을 이용해서 작업 횟수 만큼 최대값들에 대해 하나씩 빼주면 될 것 같았다.
하지만, python에 max heap이 없기 때문에 키 값을 음수화 시켜서 진행하고, tuple과 같은 부분을 사용하기 위해 heapq 모듈대신 heapq모듈이 내부적으로 이용 된 queue의 PriorityQueue를 사용하였다.
결과
통과하였다.
리뷰
리뷰도 별 다를것이 없었고, 코드 량을 줄이는 정도의 리뷰만 있었다.
no값 만큼 순차적으로 선회하기 때문에for _ in range(no):로 사용하여도 됨.list comprehension을 이용result = sum([work_tuple ** 2 for work_tuple in priority_que.queue])
로 표현 가능
두번째 풀이
소스
from heapq import heapify, heappush, heappop
def solution(no, works):
works = [x * -1 for x in works]
heapify(works)
for _ in range(no):
max_work = heappop(works) # 가장 많이 남은 작업 pop
heappush(works, max_work + 1) # 작업 수행 후 다시 heap에 넣는다.
return sum(work ** 2 for work in works)설명
위 풀이에 대해 코드를 pythonic하게 하였다.
결과
통과
