문제 보러 가기 👈 클릭!
answer의 초기값은 끝까지 주식의 값이 내려가지 않았을경우의 값으로 채운다.
=> answer = [len(prices)-1,len(prices)-2, ... , 1, 0 ]
prices를 반복하며 stack에 price의 위치(인덱스)를 추가한다.
이때, 현재 price가 stack[-1]에 있는 위치의 price보다 작을경우
즉, 주식가격이 내려갔을경우 현재price가 stack[-1]에 있는 위치의 price이상일때까지 stack.pop()한다. pop()한 위치의 answer의 값을 현재위치 - pop()한 위치 의 값으로 변경한다.
=> ex) 4번째에서 2번째 주식의 값이 내려갔을 경우
주식의 값이 떨어지지 않은 기간 = (2번째 -> 3번째 -> 4번째) = 4 - 2 = 2초
def solution(prices):
answer = [n for n in range(len(prices)-1, -1, -1)] #reverse사용해도 됨
stack = []
for i, val in enumerate(prices):
#가격이 떨어지면 그 가격보다 큰 가격이 없을때까지 pop
while stack and val < prices[stack[-1]]:
last = stack.pop()
answer[last] = i - last
stack.append(i)
return answer
📝 파이썬알고리즘인터뷰의 빗물트래핑, 온도 문제와 유사