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

programmers.co.kr/learn/courses/30/lessons/42586

코딩테스트 연습 - 기능개발

다른사람들 풀이를 보니 O(N^2)풀이가 많아 '이러면 스택을 쓰는 의미가 없지않나' 생각이 들었다.

deque를 사용해 popleft()와 appendleft()를 통해 O(1)에 풀이를 해보았다.

 

import math
from collections import deque
def solution(progresses, speeds):
    stack, answer = deque(), []
    for i in range(len(speeds)):
        # stack에 100%까지 남은 일수를 계산해서 append해준다
        stack.append(math.ceil((100 - progresses[i]) / speeds[i]))
    
    # y에 첫 기능이 며칠 뒤에 배포되는지 넣고 cnt = 1 초기화
    cnt = 1
    y = stack.popleft()
    while stack:
        # stack에 원소가 존재하는 동안 0번째 index를 pop해서 y와 비교한다
        x = stack.popleft()
        if x <= y:
            # x <= y이면, 앞의 기능이 배포될 때 같이 배포할 수 있으므로 cnt 1증가
            cnt += 1
        else:
            # x > y이면, 앞의 기능이 배포되는 날에 같이 배포를 못하므로 answer에 cnt를 append해주고 stack에 x를 다시 넣는다.
            # cnt = 1로 다시 초기화해주고 stack의 0번째 index를 pop해서 y에 넣어준다.
            answer.append(cnt)
            stack.appendleft(x)
            cnt = 1
            y = stack.popleft()
    
    # 마지막에 남은 cnt를 answer에 append해준다
    answer.append(cnt)
    
    return list(answer)

(프로그래머스 level: 2)