프로그래머스 주식가격

문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한 사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

내 풀이

1. prices를 큐에 삽입한다.
2. 스택이 비어 있는 경우 스택에 prices에서 꺼내서 본인 인덱스와 queue_price를 저장한다. 
   stack.append((queue_index, queue.popleft()))

3. 비어있지 않은 경우, prices의 맨 앞 값과 스택의 맨 위 price 값을 비교한다.
   큐의 맨 앞이 더 작다면 answer[stack_index] = queue_index - stack_index(두 인덱스간 거리) 형태로 저장한다.

   큐의 맨 앞이 더 크다면 큐에서 꺼내어 스택에 삽입한다.
   stack.append((queue_index, queue.popleft()))

4. 만약 큐가 모두 비어버리면, 두 인덱스 간 거리를 구해서 answer에 저장한다. 
   while stack : 
        stack_index, stack_price = stack.pop()
        answer[stack_index] = total_prices_length - stack_index - 1

내 코드

from collections import deque

def solution(prices):
    answer = [0 for _ in range(len(prices))] 

    total_prices_length = len(prices)
    queue = deque(prices)
    stack = []
    queue_index = 0

    while queue :
        queue_price = queue[0]

        if stack and queue_price < stack[-1][1] :
            stack_index, stack_price = stack.pop()
            answer[stack_index] = queue_index - stack_index
            continue 

        stack.append((queue_index, queue.popleft()))
        queue_index += 1

    while stack : 
        stack_index, stack_price = stack.pop()
        answer[stack_index] = total_prices_length - stack_index - 1

    return answer

결과

반성할 점

처음에 큐와 반복문을 이용해 풀었다. 하지만 시간초과로 통과하지 못했다.
항상 로직 생각 후, 시간 복잡도를 고려해서 풀 수 있을지 없을지 먼저 생각하자 !!
문제를 푼 후, 어떤 점을 개선할 수 있을지 고민해보자(중복 코드 제거, 가독성 증가 등등)