[프로그래머스/Level2] 주식가격(Python)

문제 접근

문제는 쉽다고 생각한다.

1. 맨 앞에 원소 꺼냄
2. 남은 원소 중에 작은거 순회하면서 시간 초 증가

근데 여기서 문제가 "1. 맨 앞에 원소 꺼냄"이다.
일반 list를 쓴다면 정확성은 맞겠지만, 효율성에서 시간 초과가 뜰 것이다.

핵심은 deque이다.
deque의 popleft()가 O(1)의 시간복잡도라서 그렇다.(list.pop(0)보다 빠름)

소스 코드

from collections import deque
from typing import Deque

def solution(prices):
    nprices = deque(prices)
    answer = []
    
    while nprices:
        cur = nprices.popleft()
        answer.append(calculateSeconds(nprices, cur))
    
    return answer

def calculateSeconds(prices: Deque, cur: int):
    if len(prices) == 0:
        return 0
    
    sec = 1
    for i in prices:
        if i < cur:
            return sec
        
        sec += 1
        
    return len(prices)