[python] 프로그래머스 - 주식가격

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

코딩테스트 연습 - 주식가격

문제 설명

스택을 사용해서 주식 가격이 떨어지지 않은 기간을 기록하는 문제. (자세한 설명은 프로그래머스 페이지 참고 바람)

문제 접근 및 풀이

 이는 이전에 풀었던 리트 코드 문제와 매우 유사하다. 다만 리트 코드 문제에서는 증가점을 추적하는 것이라면 여기서는 감소점을 추적한다. 따라서 주식가격이 non-decreasing order일 경우에는 계속 스택에 push하고, 아니면 pop해서 어느 정도 기간 동안 해당 인덱스가 스택에 머물러 있었는지를 기록한다. 이때 스택은 인덱스를 담고 있는 스택이므로, 현재 인덱스와 스택의 top 인덱스의 차이를 기록하면 될 것이다.

    1) 인덱스를 push하는 스택
    2) prices를 탐색하면서, non-decreasing order면 스택에 push
    3) 가격이 떨어지면, stack에서 pop한 후에 answer의 현재 인덱스 자리에 현재 인덱스와 top의 차이를 기록함.
    4) prices 탐색이 끝나면 stack의 남은 원소(가격이 떨어지지 않은 경우)들을 모두 pop하고, 
    다시 현재 인덱스와 top의 차이를 기록함.

def solution(prices):

    answer = [0 for i in range(len(prices))]
    stack = []
    for idx, price in enumerate(prices):
        while stack and (price < prices[stack[-1]] or idx == len(prices)-1):
            top = stack.pop()
            answer[top] = idx - top
        
        stack.append(idx)
    """
    while stack:
        top = stack.pop()
        answer[top] = idx - top
    """    
    return answer

 코드 중 주석처리 된 부분은 원래 4) 부분에 해당하는 것이었으나, 위의 for loop 내의 while 문에서 4)를 충분히 수행 가능(for loop을 탈출하여 while 문을 따로 작성하지 않고, for loop의 마지막 반복에서 모두 pop시키도록 함. 다만, stack이 empty가 되기 전까지 해야 하므로 while stack은 and 처리 해준다)하므로 삭제하였다.