[프로그래머스/Lv2] 주식가격 - Python

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

프로그래머스

 

비슷한 문제로 백준에서 17298번 오큰수 풀었던 기억이 났다.

그때도 스택으로 풀었던 거 같아서 이번에도 스택으로 풀어보려고 했는데 꽤 시간이 걸렸다.

오큰수는 배열을 거꾸로 순회하면서 스택에 int 하나만 저장하고 오큰수가 될 수 없는 값을 pop 하면서 풀이했는데,

이 문제는 주식가격 유지 시간을 구해야했기 때문에 순서대로 순회하면서 가격과 idx를 튜플로 스택에 append했다.

 

# 스택

def solution(prices):
    n = len(prices)
    # 초기 answer : 가격이 떨어지지 않았을 경우로 초기화
    answer = [i for i in range(n - 1, -1, -1)]
    stack = []

    for j in range(n):
		
        # 스택에 이전 주식이 남아있을 경우
        while stack:
        	# 현재 주식보다 가격이 클 경우 (스택에 남아있는 주식이 현재 시점에 떨어지는 경우)
            if stack[-1][0] > prices[j]: 
            	# 스택에서 제거 후, 떨어진 시간 계산하여 answer 갱신
                price, idx = stack.pop()
                answer[idx] = j - idx

            else:
                break

        stack.append((prices[j], j))

    return answer