프로그래머스 주식가격

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

프로그래머스

문제분석

• 주어진 배열 prices의 길이 제한사항이 >10^5이므로 사용할 수 있는 시간복잡도는 O(n)이나 최소 O(nlogn)에 끝내야한다. 따라서 완전탐색은 불가능(n^2)하고 다른 아이디어를 사용해야한다.
• 이떄 메모리를 사용해서 시간복잡도를 낮추기위해서 주어진 배열을 스택에 넣고 이를 기본의 배열과 비교하는 방법 선택
  
  
  

def solution(prices):
    answer = [0] * len(prices)
    stack = []
    for cur_day, cur_price in  enumerate(prices):
        while stack and stack[-1][1] > cur_price:
            pre_day, _ = stack.pop()
            answer[pre_day] = cur_day - pre_day
        
        stack.append((cur_day,cur_price))
        
    # 더 낮은 값이 없는 경우 처리
    while stack:
        day, _ = stack.pop()
        answer[day] = len(prices) - day -1
    return answer