초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
prices
return
[1, 2, 3, 2, 3]
[4, 3, 1, 1, 0]
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
주의사항
풀이
prices
return
[1, 2, 3, 2, 3]
[4, 3, 1, 1, 0]
stack 을 이용해보자.
(top)[stack] 이 있다.
[1]
[2,1]
[3,2,1]
2 가 stack 의 top 보다 작다.
2 보다 작거나 같은 stack 의 top 이 나올때 까지 pop 해준다.
답에는 변화를 일으킨 값의 index (3) 에서 원래 자신의 index (2) 를 빼준 값 1을 append 해준다.
[2,2,1]
[3,2,2,1]
모든 값을 넣었다.
남아있는 값은 모두 pop 하여 prices 의 전체 길이 - 1 - 자신의 index 를 append 해주자.
내 풀이 코드
import collections
def solution(prices):
answer = [0 for _ in range(len(prices))]
stack = collections.deque()
for index, price in enumerate(prices) :
while stack and stack[0][0] > price:
current_top = stack.popleft()
answer[current_top[1]] = index - current_top[1]
# 가격(price) 뿐 아니라 index 까지 같이 넣어주는 이유는,
# 원래 `prices` 에서 어느 index 인지 빠르게 파악하기 위해서이다.
# 그래야만 위의 while 문에서 정답 처리를 할 때 O(1) 으로 처리할 수 있다.
stack.appendleft((price, index))
# 남은 값들 처리
for price, index in stack:
answer[index] = len(prices) - 1 - index
return answer
