1. 문제에 대한 이해
- 우리가 풀어야 할 문제는 무엇인가?
- 주어진 자료는 무엇인가?
- 조건은 무엇인가?
- 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
- 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.
- 우리가 풀어야 할 문제
-> 가격이 떨어지지 않은 기간은 몇 초인지 return
- 조건은 무엇인가?
-> 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어짐
-> prices의 길이는 2 이상 10만 이하
2. 계획
- 전에 비슷한 문제를 알고 있는가?
- 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
- 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
- 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
- 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
- 자료는 모두 사용했는가?
- 조건을 모두 사용했는가?
- 문제에 포함된 핵심적인 개념은 모두 고려했는가?
- 2차원 for문은 불가능하다
-> 길이가 10만이기 때문에
- 스택을 활용할 수 있는가?
-> for문을 하나만 활용해서 문제를 풀 수 있는가?
->
- 왜 4인가?
-> 떨어지지 않았기 때문에
stack에 넣는다
3
2
1
1을 넣는다
그 다음 2가 나오면 2를 넣는다
그 다음 3이 나오면 3을 넣는다
-> 이렇게 위에 쌓는다
-> 만약 작은 수가 나왔다면?
-> 2
-> 해당 위치의 수와 스택의 원소 개수를 빼준다
3
2
1
1, 2, 3, 2, 3
1 3 5 3 1
4 3 1 1 0
- 스택을 어떻게 활용하는가?
->
3
2
1
3. 실행
- 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
Stack<Integer> stk = new Stack<>();
for(int i=0; i<prices.length; i++){
while(!stk.isEmpty() && prices[i] < prices[stk.peek()]){
answer[stk.peek()] = i - stk.peek();
stk.pop();
}
stk.push(i);
}
while(!stk.isEmpty()){
answer[stk.peek()] = prices.length-stk.peek()-1;
stk.pop();
}
return answer;
}
}4. 반성
- 문제를 다른 방식으로 해결할 수 있는가?
- 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?
- 풀이를 참고해서 풀었다.
-> answer라는 배열을 선언한다는 점,
while문을 통해서 검사를 한다는 점. 그리고 검사 시에는 조건을 만족한다면 계속 순회한다는 점
stack을 활용하는데, stack에는 원소의 값이 아닌 위치를 저장해준다는 점
-> 이 3가지가 핵심이다 .
-> 이 아이디어들을 잘 숙지하고 다른 문제들을 풀 때 적용해보자.
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
-> 배열을 활용하면 된다는 점
스택에 index를 저장해주면 된다는 점을 알았다면
더 효율적으로 문제를 해결할 수 있었을 것이다.