Programmers: 주식 가격

문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

입출력 예
prices	        return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

 

스택을 이용하는 문제이다. 가격이 오르는동안은 stack에 인덱스와 가격을 push하고, 이전보다 가격이 내려간 경우, 해당 가격보다 높은 가격이 나올 때까지 stack에서 pop해서 기간을 입력하는 방식이다. 결과적으로 stack은 증가하는 monotone stack이 된다. 

마지막까지 stack에서 뽑히지 않은 것들은 가격이 내려간 적이 없다는 의미이므로, 전체 시간에서 해당 가격이 나타난 시간을 뺀 값을 입력한다. 

def solution(prices):
    answer = [0 for _ in range(len(prices))]
    stack = []
    for i in range(len(prices)):
        while stack and prices[i] < stack[-1][1]:
            (idx, last_price) = stack.pop()
            answer[idx] = i-idx                
        stack.append((i, prices[i]))
    
    while stack:
        (idx, last_price) = stack.pop()
        answer[idx] = len(prices)-1-idx
        
    return answer

링크: programmers.co.kr/learn/courses/30/lessons/42584?language=python3