* [파이썬] [스택/큐] Pro 주식가격

문제

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

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

 

코드

def solution(prices):
    answer = [] *len(prices)
    
    for i in range(len(prices)):
        index=-1
        for j in range(i+1, len(prices)):
            if prices[i]>prices[j]:
                index=j
                break
        if index==-1:
            answer.append(len(prices)-i-1)
        else:
            answer.append(index-i)
    return answer

생각 정리

스택을 이용하면 시간 복잡도를 더 줄일 수 있다.

def solution(prices):
    answer = [0]*len(prices)
    stack = []
 
    for i, price in enumerate(prices):
        #stack이 비었이면 false
        while stack and price < prices[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
 
    # for문 다 돌고 Stack에 남아있는 값들 pop
    while stack:
        j = stack.pop()
        answer[j] = len(prices) - 1 - j
 
    return answer


출처: https://deftkang.tistory.com/175 [deftkang의 IT 블로그]

스택으로 푸는 방법은 처음 price를 stack에 쌓고 다음 price가 더 크면 스택에 쌓고 작으면 pop을 한다.