91. 기능개발

[문제]

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

 

[풀이]

1. deque 자료구조를 통해 조건을 만족하면 해당 작업을 popleft() 함수를 통해 제거하려고 한다.

2. 우선 진행률과 속도를 zip으로 묶어서 deque로 만들어주고

3. 모든 작업이 끝날 때까지 while문으로 반복해준다.

4. deque를 진행률을 업데이트 하면서 완료된 작업을 제거해준다.

5. 완료된 작업이 있다면 (count > 0) 그 개수를 반환 리스트에 추가해주자.

from collections import deque
def solution(progresses, speeds):
    answer = []
    queue = deque(zip(progresses, speeds))
    count = 0

    while queue:
        queue = deque((p + s, s) for p, s in queue)

        while queue and queue[0][0] >= 100:
            count += 1
            queue.popleft()

        if count:
            answer.append(count)
            count = 0

    return answer

 

 

시간복잡도를 고려한다면 다음과 같이 풀 수 있다.

1. 배포그룹을 저장할 리스트를 생성하고 진행률과 속도를 묶어서 순회한다.

2. 배포그룹이 비었다면 [남은 작업일 수와 , 배포그룹 수] 를 저장한다.

3. 다음으로 현재 진행중인 작업이 이전 작업의 남은 작업일 수보다 크다면 새로운 배포그룹으로 저장한다.

4. 작다면 기존 배포그룹의 수를 1 증가시켜준다.

5. 배포그룹을 저장한 리스트에서 배포그룹의 수만 가져와서 반환한다.

def solution(progresses, speeds):
    Q = []
    
    for p, s in zip(progresses, speeds):
        
        if len(Q) == 0 or Q[-1][0] < -((p-100)//s):
            Q.append([-((p-100)//s), 1])
        else:
            Q[-1][1] += 1
    
    return [q[1] for q in Q]