내가 푼 풀이
from collections import deque
import math
def solution(progresses, speeds):
answer = []
workday = deque([])
for progress, speed in zip(progresses, speeds):
workday.append(math.ceil((100 - progress) / speed))
idx = -1
max = 0
while workday:
cur = workday.popleft()
if(max < cur):
max = cur
idx += 1
answer.append(1) #새로운 배포 시작
else:
answer[idx] += 1
return answer이 문제는 "뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다"라는 지문을 통해 선입 선출, 즉 큐 자료구조를 사용하면 된다는 것을 알 수 있다.
큐 자료구조를 이용할 때에는 list보다 deque를 사용하는 것이 훨씬 효율적인데, 그 이유는 pop을 할 때 list의 경우 한 칸씩 다시 재배열이 되기 때문에 시간이 오래걸리기 때문이다.
먼저 zip 함수를 이용해 각 기능의 작업완료 시간을 구했고, 여기서 2.1일이 걸리든 2.8일이 걸리든 모두 3일이 걸리는 것으로 취급하기 때문에 math.ceil 함수를 사용했다. 베스트 풀이에서는 ceil함수 대신 - 등호를 붙여 내림한 음수를 사용했던데, ceil함수의 사용 여부에 따라 실행 속도가 차이가 나는지는 확인해봐야할 것 같다.
큐이기 때문에 앞에서부터 하나씩 pop 하면서, 현재 배포 작업의 최대 작업일 수가 자기 자신보다 크면(ex. 내 앞에까지는 10일만에 배포가 가능한데, 나는 20일이 걸리는 작업이라면) 새로운 배포가 시작될 수 있도록 로직을 구현했다.
주의할 점은
progresses = [99, 99, 99, 99, 99, 99]
speeds = [1, 1, 1, 1, 1, 1]이 경우에는 [1, 1, 1, 1, 1, 1] 이 답이 아니라 [6]이 답이므로 max <= cur이 아니라 max < cur임에 유의해야한다!
(등호 조건 넣어서 여러 번 틀림 ㅎㅎ)
