[프로그래머스] 스택/큐, 주식가격

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

프로그래머스

개요

prices: 초 단위로 기록된 주식가격이 담긴 배열

return: 가격이 떨어지지 않은 기간은 몇 초인지

[1, 2, 3, 2, 3] → [4, 3, 1, 1, 0]

 

 

나의 코드

from collections import deque

def solution(prices):
  answer = []
  idx_prices = deque(enumerate(prices))
  for _ in prices:
    idx, n = idx_prices.popleft()
    t = len(prices)-idx
    for i in range(t):
      if i == t-1:
        answer.append(t-1)
      else:
        if n > prices[idx+i+1]:
          answer.append(i+1)
          break
        else:
          continue
  return answer

 

정답 도출은 쉬웠으나, 시간 효율 문제 개선이 어려웠음.

• for _ in range(len(prices)-idx)에서 len 부분이 시간복잡도 심각.
  어차피 _ 사용할 거 아니라면,  for _ in prices로 대체
• 하나의 for문 안에 len(prices)-idx를 여러번 사용하였는데, 실행마다 len의 시간복잡도가 거듭되므로,
  t라는 변수에 저장한 후 t를 호출하는 게 훨씬 나음
• list 사용을 최소화할 것! reverse문도 안 먹혔던 이유 → queue와 deque를 이용하자 (pop, popleft..)
• enumerate 사용하지 않을 방법 모색해보자.

 

시간 초과 (실패) 코드

from collections import deque

def solution(prices):
  answer = []
  idx_prices = deque(enumerate(prices))
  for _ in range(len(prices)):
    n = idx_prices.popleft()
    try:
      small_idx = [x[0] for x in idx_prices if x[1]<n[1]][0]
      answer.append(small_idx-n[0])
    except:
      answer.append(len(prices)-n[0]-1)

  return answer

- try, except 이하가 애초에 비효율적이긴 하였음: 리스트 모두 완성 후 첫번째 원소만 사용하는 것이기 때문.

- 이외 이유는 상단에 기술.

 

모범 코드

1. 큐 활용

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()

        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1

        answer.append(count)

    return answer

2. 빠르며 깔끔

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        if stack != []:
            while stack != [] and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer