문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
| progress | speeds | return |
|---|---|---|
| [93, 30, 55] | [1, 30, 5] | [2, 1] |
| [95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
풀이
def solution(progresses, speeds):
queue = []
answer = []
for progress, speed in zip(progresses, speeds):
queue.append([progress, speed])
while len(queue):
for i in range(len(queue)):
if sum(queue[i]) < 100:
queue[i][0] = sum(queue[i])
else:
queue[i][0] = 100
count = 0
for i in range(len(queue)):
if queue[i][0] != 100:
break
count += 1
if count:
answer.append(count)
queue = queue[count:]
return answer해결 과정
-
큐를 사용하면 해결할 수 있을 것이다.
이 문제는 특성상 먼저 들어온 작업이 먼저 나가지 않는 이상 다른 작업은 100%가 되었어도 나갈 수 없다. 그렇다면 FIFO 성질을 지니는 큐의 동작방식을 생각하면 되지 않을까? -
각 기능별로 작업속도를 매칭해줘야 한다.
맨 처음의 작업이 100%가 되면 작업이 나가게 된다. 그렇게 되면 큐의 길이가 줄기 때문에 인덱스를 사용하면 불안정해진다.물론 speeds에서도 100%가 된 작업을 제거한다면 둘을 zip으로 묶어서 합하면 되지만, 처음에 큐에 넣을 때 둘을 하나로 묶어서 넣으면 간단하지 않을까?
-
작업 진행량이 100이 넘어가지 않도록 하자.
물론 100이 넘어가게 해도 문제를 해결할 수는 있다. 단지, 이는 문제에 더 적합하게 만들뿐이다. -
큐에 있는 첫 작업이 100%인지 확인하자.
모든 작업의 작업량을 증가시켰다면 큐에 있는 첫 번째 작업의 진행률이 100%인지 확인해야 한다. 언제 해당 작업이 100%가 되었을지 모르기 때문이다. -
큐의 길이를 조절하라.
count의 값을 통해 반복문을 돌려 pop을 하는 방법도 있다. 아니면, 먼저 pop을 하고 값을 비교해 다시 큐에 넣을지, 아니면 그대로 pop할지 결정할 수도 있다.하지만, 파이썬의 인덱스 슬라이싱 기법을 사용하여 큐의 길이를 조절하는 방법도 있다.
다른 사람의 풀이
def solution(progresses, speeds):
answer = []
time = 0
count = 0
while len(progresses)> 0:
if (progresses[0] + time*speeds[0]) >= 100:
progresses.pop(0)
speeds.pop(0)
count += 1
else:
if count > 0:
answer.append(count)
count = 0
time += 1
answer.append(count)
return answer큐에 집어넣지 않고도 문제를 해결할 수 있다. 큐에 집어넣는다는 것은 기억 장소를 참조해 값을 변경하는 거지만, 단순 산술 연산의 값이라면 레지스터에 저장되기 때문에 조금 더 효율적이라고 할 수 있을 것이다.
progresses에 첫 번째로 들어있는 작업이 진행된 시간 * 작업 속도를 기존에 진행된 기능의 진행량에 더한 값이 100 이상이라면 progresses에서 pop을 수행한다. 이렇게 해도 되는 이유는 time 변수를 통해 작업이 진행된 시간을 저장하기 때문에 이후 작업도 같은 시간 동안 작업한 결과를 계산할 수 있기 때문이다.
