프로그래머스 level2 주식가격

Problem

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

Solution

내 풀이

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

브루트포스로 완전 탐색하였다.

다른 사람 풀이

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for idx, price in enumerate(prices):
        while stack != [] and stack[-1][1] > price:
            past, _ = stack.pop()
            answer[past] = idx - past
        stack.append([idx, price])
        
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
        
    return answer

스택을 이용한 풀이

현재의 price가 stack의 마지막 price보다 작은 경우, pop을 하여 정답에 idx 차이만큼 기록한다.
이 과정을 stack이 완전히 비워지거나, stack의 마지막 price가 현재 price보다 작을때까지 반복한다.

나는 브루트 포스로 완전 탐색을 함으로써 O(n^2)이지만 스택을 이용하면 O(n)으로 풀이가 가능하다.

Reference

프로그래머스 level2 주식가격 - 다른 사람 풀이