프로그래머스 2단계 "주식 가격"

문제

프로그래머스 "주식 가격"

풀이

백준 17298번유사한 문제.

스택에 차례대로 가격을 넣어주고 빼주며 스택에 존재했던 시간 만큼 answer배열에 1씩 더해준다.
다만 스택을 단순하게 이용하는 것이 아니라 인덱스를 스택에 넣는 방식으로 풀었으며, 단순히 for문 도배 후 반복하여 문제를 해결하는 것보다 훨씬 빠르게 문제를 해결할 수 있다...

Python 코드

def solution(prices):
  stack = []
  answer = [0 for _ in range(len(prices))]
  for i in range(len(prices)):
    # 스택에 담겨있는 인덱스를 이용하여 price[i]보다 높은 가격의 시점을 빼줌
    while stack and prices[stack[-1]] > prices[i]: 
      # 1초뒤에 가격이 떨어지므로 pop 해줄 때 +1을 해준다
      answer[stack.pop()] += 1

    # 스택에 담겨있는 시점들에 1초씩 더해준다
    for j in range(len(stack)):
      answer[stack[j]] += 1
    
    # 새로운 시점 추가
    stack.append(i)
  return answer