핵심 아이디어는 스택에 (현재 값을 기준으로) 값이 떨어지지 않은 주식의 인덱스를 저장하는 것이다. 매 반복마다 현재 값보다 큰 주식이 있다면, 즉 가격이 떨어진 주식이 있다면 스택에서 제거하며 정답을 갱신해준다.
prices
를 1번째 원소부터 탐색하며, 이전 원소의 인덱스를 스택에 넣는다현재 인덱스 - 가격이 떨어진 경우의 인덱스(=스택 top 값)
이다.import java.util.*;
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
Stack<Integer> stack = new Stack<Integer>();
for(int i=0; i<prices.length; i++){
answer[i] = prices.length-1-i;
}
for(int i=1; i<prices.length; i++){
stack.push(i-1);
while(!stack.isEmpty() && prices[stack.peek()] > prices[i]){
int j = stack.pop();
answer[j] = i-j;
}
}
return answer;
}
}
def solution(prices):
answer = [len(prices)-1-i for i in range(len(prices))]
stack = []
for i in range(1, len(prices)):
stack.append(i-1)
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
return answer