[프로그래머스 Lv.2] 주식가격 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

풀이

사실 이 문제는 스택 문제라고 표현되어 있긴 하나, 이중 for문으로 풀어도 제한 시간 내에 통과할 수 있는 문제이다.

 

스택을 사용한 풀이는 스택을 더 싼 가격이 나타낼 때까지 가격의 위치(인덱스)를 보관하고 있는 통으로 사용한다는 아이디어로 풀면 된다. 레벨 2 문제치고는 스택을 저런 아이디어를 가지고 사용한다는 것이 조금 어려웠던 것 같다. 

def solution(prices):
    length = len(prices)
    answer = [0 for _ in range(length)]
    stack = []
    
    for idx in range(length): # for문으로 전체 prices를 순회하며
        while stack and prices[stack[-1]] > prices[idx]: # 스택이 비어있지 않고, 현재 가격이 스택의 상단에 위치한 가격보다 작은 경우
            top = stack.pop() # 스택에서 제거
            answer[top] = idx - top # 스택에 남아있는 기간 = 가격이 떨어지지 않은 기간
        stack.append(idx) # 자신보다 큰 가격들은 모두 제거하고, 해당 idx를 스택에 저장
    
    for idx in stack: # 스택에 남아있는 idx들은
        answer[idx] = length - 1 - idx # 끝까지 가격이 떨어지지 않은 idx들
    
    return answer