[Python | 파이썬] 주식가격 (프로그래머스 STACK/QUEUE)

[Python | 파이썬] 주식가격 (프로그래머스 STACK/QUEUE)

 

 

각 가격이 최대로 가격이 떨어지지 않을 수 있는 기간으로 answer 리스트를 초기화한다.

answer = [len(prices)-1-i for i in range(len(prices))]

prices[0]은 len(prices)-1만큼 최대로 안 떨어질 수 있고, prices[n-1]은 맨 마지막 가격이므로 0이다.

현재까지의 시간(초)에 대해서 가장 높은 가격의 index를 저장하는 stack을 생성한다.

맨처음에 index가 0일때 현재 가장 높은 가격은 prices[0]이다.

1부터 len(prices)-1까지 i를 증가시키며 prices[index]가 현재 가격 prices[i]보다 크다면 prices[index]는 적어도 i - index 초 간은 가격이 떨어지지 않은 것이므로 answer[index] = i - index 로 갱신한다.

그리고 stack에서 이 원소를 제거한 뒤 stack에 남은 원소가 있다면 그 원소에 대해서도 적어도 몇 초간 가격이 떨어지지 않은 것인지 갱신해준다. stack이 비게 된다면 prices[i]가 prices[index]보다 컸던 것이므로 stack에 새로운 인덱스 i를 추가해준다. 만약 prices[index]가 prices[i]보다 작거나 같다면 stack을 변경하지 않고 반복문을 종료하고 i를 증가시킨다.

 

prices = [1, 2, 3, 2, 3] 일때

처음에 answer = [4, 3, 2, 1, 0] 으로 초기화해준다.

stack = [0]

 

- i = 1

stack[-1] = 0

if prices[0] > prices[1] 이 False이므로 반복문을 종료하고 stack에 1을 추가한다.

stack = [0, 1]

 

- i = 2

stack[-1] = 1

if prices[1] > prices[2] 가 False이므로 반복문을 종료하고 stack에 2를 추가한다.

stack = [0, 1, 2]

 

- i = 3

stack[-1] = 2

if prices[2] > prices[3] 가 True이므로 answer[2] = 3 - 2로 갱신하고 stack에서 2를 제거한다. 

아직 stack에 원소가 있으므로 계속한다.

stack = [0, 1]

stack[-1] = [1]

if prices[1] > prices[3]가 False이므로 반복문을 종료하고 stack에 3을 추가한다.

stack = [0, 1, 3]

 

- i = 4

stack[-1] = 3

if prices[3] > prices[4]가 False이므로 반복문을 종료하고 stack에 4를 추가한다.

stack = [0, 1, 3, 4]

 

반복문이 종료되고 답은 answer = [4, 3, 1, 1, 0]

def solution(prices):
    answer = [len(prices)-i-1 for i in range(len(prices))]
    stack = [0]
    for i in range(1, len(prices)):
        while stack:
            index = stack[-1]
            if prices[index] > prices[i]:
                answer[index] = i - index
                stack.pop()
            else:
                break
        stack.append(i)
    return answer

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

프로그래머스