🤔 어떻게 풀 지?..
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
//해당 가격이 시간에 흐름에 따라 가격 변동이 있다면 -1
//만약 처음~끝 그냥 2중 반복문은 100000 * 100000 = 100/0000/0000 => 100억번=
}
}🤷♂️ 2중 반복문은 바로 Pass?
처음에 20분 가량 문제 접근 자체에 대해서 고민했다.
가장 쉽게 풀 수 있는 방법으로는 2중 반복문을 생각했는데 주석으로 작성한 것처럼 시간복잡도가 넘칠 거라고 생각했고 제외하고 분명 다른 방법이 있을거라 생각했다.
서칭했더니 왠걸?..2중 반복문으로 풀이를 하신 분들이 많았다.
아무리 중간에 break 같은걸로 종료시킨다하더라도 정말 최악의 경우에는 100억에 근접하는 숫자인데 다른 풀이가 있을거라 생각했다
👍 Stack으로 하는 풀이
더 좋은 방법!
문제 자체도 세부 분류에 스택/큐 로 풀이하라고 되어있었다!
사실 잘 정리해두신 블로그를 쭉 보면서 이해를 하려고 했는데 생각보다 잘 이해가 되지 않았다. 스택 자체가 어떤 것을 의미하고 왜 이런 과정을 하느냐가 이해가 되지 않는 상황에서 결국 직접 그림을 그리면서 이해하려했다!
1. 스택에 뭘 담는거야?
이 문제를 사용하는데 어떤 부분에서? 왜? 스택을 사용하는지를 이해하고 싶었다.
직접 그리면서 이해를 하니 쉽게 이해가 가능했다.
일단은 스택에 담는 건 아직까지 주식이 유지 or 상승중이라는 의미이고
그렇기 때문에 마지막까지 남아있는 건 마지막까지 가격이 하락된 적이 없다는 의미!
아 그리고 담는 건 아직 하락되지 않은 인덱스 값을 저장!
2. 스택을 어떻게 응용?
인덱스를 하나씩 이동하면서 스택과 비교를 한다.
예를 들어 1 -> 5->4 가격 하락이 발생했다고 치자.
이 때는 스택에
ㅣ1ㅣ
ㅣ0ㅣ
ㅣ-ㅣ
이런 식으로 쌓여있을 것이고 peek를 하면 1이 나온다. 이제 그럼 peek로 나온 인덱스와 지금 비교하고 있는 인덱스를 비교해서 하락으로 가는 건지 아님 상승or유지인지를 확인한다!
- 하락 => while{ peek }(현재 인덱스 가격보다 낮은 가격인지)
- 상승or유지 => 넘어간다
3. 정리
정리하자면 스택에는 noLoss 즉 손실이 아직 안 일어난 주식 가격이 담겨있는 것이고
1초라는 시간 간격으로 마지막 초까지 반복을 하면서
상승,유지라면 스택에 넣고 반대로 하락이라면 정답 값을 갱신하고 pop해서 빼내주면 된다!
사실 이런 문제가 또 나왔을 때 스택을 이용해서 쉽게 풀 수 있을거라고 생각은 안 든다.
하지만 0~끝을 탐색하면서 상승 하락 유지 등을 체크하는 문제에서는 stack을 사용해보자라는 생각을 가지면 될 것 같다!
💻 CODE
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
Stack<Integer> noLoss = new Stack();
int[] answer = new int[prices.length];
for(int i = 0 ; i < prices.length; i++){
//스택 안에 값 존재 + stack최상단 > 지금꺼내는거
while(!noLoss.isEmpty() && prices[noLoss.peek()] > prices[i]){
//ans 갱신
answer[noLoss.peek()] = i - noLoss.peek();
noLoss.pop();
}
noLoss.push(i);
}
//아직 남아있는 스택들 계산
//=> 마지막까지 감소하지 않은 녀석들
while(!noLoss.isEmpty()){
answer[noLoss.peek()] = prices.length - noLoss.peek() - 1;
noLoss.pop();
}
return answer;
}
}