[프로그래머스/Lv.2] 주식가격 | 스택 | 파이썬

문제

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

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

 

제한사항

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

 

입출력 예

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

나의 풀이

def solution(prices):
    n = len(prices)
    stack = []
    answer = [n - 1 - i for i in range(n)]
    
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] > price:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)
    
    return answer

`answer` 리스트의 초기값은 각 가격이 끝까지 떨어지지 않았을 때를 기준으로 한다.

예를 들어 `prices`의 길이가 `5`인 경우, `answer`의 초기값은 `[4, 3, 2, 1, 0]`이 된다.

스택을 이용해 n초 뒤에 가격이 떨어졌을 때만 이 값을 업데이트해준다.

 

스택에 가격의 인덱스들을 하나씩 넣으면서

스택의 마지막 값을 인덱스로 가지는 가격이 현재 가격보다 큰 경우

몇 초 뒤에 가격이 떨어졌는지를 인덱스를 이용해 계산해서 `answer`의 해당 인덱스의 값을 업데이트한다.

 

회고

어제 풀었던 뒤에 있는 큰 수 찾기와 비슷한 유형의 문제라 금방 풀 수 있었다!