[프로그래머스] 기능 개발 1

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

---

아이디어

스택/큐 카테고리로 분류되어 있지만 스택이나 큐를 이용하지 않은 방법으로 풀었다. 

먼저 모든 작업에 대해서 작업에 소요되는 시간을 계산해서 리스트를 만든다.

 

입출력 예 #2 기준으로 [5, 10, 1, 1, 20, 1]가 된다. 

첫 번째 작업은 기다릴 필요가 없기 때문에 바로 출력할 수 있다.

 

두 번째 작업은 10일이 걸린다. 따라서 세 번째, 네 번째 작업은 1일밖에 걸리지 않았지만 두 번째 작업이 완료될 때까지 기다려야 한다. 즉 10일째에 배포될 수 있다. 

 

다섯 번째 작업이 20일이 걸리기 때문에 여섯 번째 작업도 1일만에 끝이 났지만 20일째에 배포될 수 있다. 

 

한 번에 배포된 작업들을 기준으로 소요된 시간을 보면 [5], [10, 1, 1], [20, 1]이라고 할 수 있다. 

 

첫 번째 작업부터 순회하면서 이전까지 나온 작업 시간의 최댓값과 비교한다.

i번째 작업에 걸린 시간이 ( i - 1 )번째 작업까지 소요시간의 최댓값보다 크다면, (즉, 이때까지 중에서 가장 큰 값일 때,) 

앞에 남아있던 작업들은 i번째 작업이 배포되기 전에 배포될 수 있게 된다. 

> 첫 번째 작업에 소요된 시간은 5로 최대 소요 시간이 된다.

>> Max = 5로 update

 

> 두 번째 작업에 소요된 시간은 10으로, 두 번째 작업이 배포되기 전에 첫 번째 작업이 배포될 수 있게 된다.

>> Max = 10으로 update

 

> 다섯 번째 작업에 소요된 시간은 20으로, 다섯 번째 작업이 배포되기 전에 2, 3, 4번째 작업이 배포될 수 있다. 

>> Max = 20으로 update 

 

이렇게 하면, 한 번에 배포되는 작업의 수를 알 수 있다. 즉 구간의 시작점이 1, 2, 5이기 때문에 (1), (2,3,4), (5,6)이 되는 것이다. 그리고 마지막 작업을 고려하기 위해서 전체 작업의 개수를 append한다.

 

인덱스를 기준으로 했기 때문에 시작점의 인덱스를 담은 배열은 [0, 1, 4, 6]가 된다. 

 

i번째와 i-1번째의 차이를 계산하면 [1, 3, 2]라는 값을 얻을 수 있다.

---

Solution

import math 
def solution(progresses, speeds):
    answer = []
    time_taken = [math.ceil((100 - x) / y) for x, y in zip(progresses, speeds)]
    
    Max = -1
    interval_idx = []
    for i in range(len(time_taken)) : 
        if time_taken[i] > Max : 
            Max = time_taken[i]
            interval_idx.append(i)
        
    interval_idx.append(len(time_taken))
    for i in range(1, len(interval_idx)) : 
        answer.append(interval_idx[i] - interval_idx[i-1])
    return answer