🎯문제 해석
문제는 이해가 갔지만 어떻게 풀어야 할지 머리를 계속 굴렸지만 단번에 떠오르지 않았다. 쉽게 풀리진 않아서 스택/큐 카테고리에서 가장 마지막 섹션에 있는 것 같다. 가장 처음에는 스택을 이용해서 (값, 인덱스)를 담아서 스택에 있는 값보다 같거나 작도록, 혹은 같거나 크도록 바꿔가며 실험해봤다. 2-3-2-3 이러한 숫자가 있을때 가장 처음 2는 답이 4가 나오도록 해야하는데, 스택을 활용해서 어떤 방법으로 풀어나가야 할지 더 자세하게 떠오르지 못했다. 특히 나는 '값'으로 스택에 넣을지 말지 고민했지만 '인덱스'로 스택에 넣는 건 생각을 못했던 것 같다.
✅이중 for문을 통한 풀이방법
int answer = new int[prices.length];
for(int i=0;i<prices.length;i++){
for(int j=i+1;j<prices.length;j++){
if(prices[i]<= prices[j]){
answer[i]++;
}else{
break;
}
}
}
return answer;✅스택을 통한 풀이방법
초점을 둬야할 것은 인덱스에서 얼만큼 떨어진 곳에서 주식이 떨어졌느냐다. 따라서 스택에는 인덱스값을 넣고 prices[i]와 스택의 peek()를 비교하면서 넣고 빼고를 반복해주면 된다.
인덱스 i : 0 1 2 3 4
prices[i] : 1 2 3 2 3
answer :
이렇게 세팅되어있다고 해보자
i=0일때, 스택은 비어있으므로 스택에 0이 들어간다.
현재 스택 : (top)0
인덱스 i : 0 1 2 3 4
prices[i] : 1 2 3 2 3
answer :
i=1일때, 스택에는 0이 있고, prices[0] <= prices[1] 즉 1<=2 이므로 while문에는 들어가지 않고 바로 스택에 1이 들어간다.
현재 스택 : (top)1 0
인덱스 i : 0 1 2 3 4
prices[i] : 1 2 3 2 3
answer :
i=2일때, 스택의 peek() = 1이고 prices[1] <= prices[2] 즉 2<=3이므로 while문에 들어가지 않고 바로 스택에 2가 들어간다.
현재 스택 : (top)2 1 0
인덱스 i : 0 1 2 3 4
prices[i] : 1 2 3 2 3
answer :
i=3일때, 스택의 peek() = 2이고 prices[2]>prices[3] 즉 3>2이므로 while문을 돌아서 answer[3] = 1이 들어간다.
현재 스택 : (top)1 0
인덱스 i : 0 1 2 3 4
prices[i] : 1 2 3 2 3
answer : 1
이후엔 스택의 peek() = 1 이고 prices[1] <= prices[3]이므로 바로 while문에 들어가지 않고 스택에 3이 들어간다.
현재 스택 : (top)3 1 0
인덱스 i : 0 1 2 3 4
prices[i] : 1 2 3 2 3
answer : 1
i=4일때, 스택의 peek() = 3 이고 prices[3] <= prices[4] 이므로 바로 while문에 들어가지 않고 스택에 4가 들어간다.
현재 스택 : (top)4 3 1 0
인덱스 i : 0 1 2 3 4
prices[i] : 1 2 3 2 3
answer : 1
이후엔 스택에 남아있는 모든 값이 주식이 떨어지지 않았다는 것이므로 stack을 pop하면서 answer[idx] = prices길이 - idx - 1 을 해주면 끝난다.
Stack<Integer> stack = new Stack<>();
for(int i=0;i<prices.length;i++){
while(!stack.isEmpty() && prices[stack.peek()] > prices[i]){
int idx = stack.pop();
answer[idx] = i-idx;
}
stack.add(i);
}
while(!stack.isEmpty()){
int idx = stack.pop();
answer[idx] = prices.length - idx - 1;
}