[프로그래머스] 주식가격

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42584

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

 

prices의 길이를 n이라고 하면, 최대 O(nlogn)의 풀이가 가능해 보였다.

스택을 이용해서 문제의 요구사항대로 구현하고자 했다. 

스택의 top에 있는 주식의 price가 추가하려고하는 주식의 price보다 같거나 작으면 그냥 스택에 push하고, 크면 스택 top 주식의 price가 추가하려고하는 주식의 price보다 같거나 작아질 때까지 pop을 한다.

따라서 스택을 이용한 풀이의 최종 시간 복잡도가 O(n)가 된다.

def solution(prices):
    # prices의 길이 : 1 <= n <= 100000
    # 최대 O(nlogn) 정도 가능
    
    n_prices = len(prices)
    answer = [0 for _ in range(n_prices)]
    
    stack = [(prices[0], 0)] # (주식 가격, stack에 push된 시점)
    for i, price in enumerate(prices):
        top_price = stack[-1][0]
        
        if top_price > price:
            # top_price <= price가 될 때까지 pop한 후에 push
            while top_price > price:
                stack_top = stack.pop()
                answer[stack_top[1]] = i - stack_top[1]
                
                if len(stack) == 0:
                    break
                
                top_price = stack[-1][0]
            
        stack.append((price, i))
    
    
    while len(stack) > 0:
        stack_top = stack.pop()
        answer[stack_top[1]] = n_prices - 1 - stack_top[1]
    
    # 최종 복잡도 : O(n)
    return answer