https://school.programmers.co.kr/learn/courses/30/lessons/42584
- O(N^2) 시 시간 초과
- O(N)으로 풀이 생각
- 현재 기준으로 떨어진 적이 없다면 전체 크기-현재 index
- 떨어진 적이 존재한다면, 뒤에 나타난 주식에서 앞에 데이터들을 처리함으로써 떨어진 index-앞 주식 index를 갱신시켜 한번만 순회
1
2
3
4
5
6
7
8
9
10
11
12
def solution(prices):
n = len(prices)
answer = [n-i for i in range(1,n+1)]
que = []
for i, price in enumerate(prices):
while que and que[-1][0] > price:
_, index = que.pop()
answer[index]= i-index
que.append((price, i))
return answer