🎯문제
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
| prices | return |
|---|---|
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
✏️풀이
코드
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
// prices 배열의 길이만큼 배열 생성
int[] answer = new int[prices.length];
// 값을 저장할 스택
Stack<Integer> value = new Stack<>();
// 인덱스를 저장할 스택
Stack<Integer> index = new Stack<>();
for(int i = prices.length - 1; i >= 0; i--) {
// 스택이 비어있지 않고, value의 값이 크거나 같을 경우
while(!value.isEmpty() && value.peek() >= prices[i]) {
// 값과 인덱스를 제거
value.pop();
index.pop();
}
// 스택이 비어있지 않다면
if(!value.isEmpty()) {
// 해당 값이 있는 인덱스에서 현재 위치를 빼줌
answer[i] = index.peek() - i;
}
// 스택이 비어있다면
else {
// 마지막 인덱스에서 현재 위치를 빼줌
answer[i] = (prices.length - 1) - i;
}
// 값과 인덱스를 저장
value.push(prices[i]);
index.push(i);
}
return answer;
}
}설명
해당 문제는 스택으로 해결을 할 수 있었다. 보통은 스택 하나로 해결을 했었지만, 이 문제는 다른 방식이 생각나지 않아 스택을 2개를 만들어서 해결을 해보았다. 다른 더 좋은 방법들이 있겠지만 이 방법은 "재밌네?"라는 생각이 들수도 있을 것 같다.
실제로 풀면서 이게 되네? 라는 생각을 했다 :)
배열의 값을 저장할 스택, 배열의 인덱스를 저장할 스택 2개를 생성한다.
이후 반복문을 지나면서 스택이 비어있지 않고 스택에 저장된 값이 비교할 위치의 배열의 값보다 크거나 같을 경우 스택에서 값을 제거한다. 이때 값을 제거했다면 해당 위치를 저장한 인덱스 스택에서도 값을 제거해주는 것이 중요하다.
만일 스택이 비어있지 않다면 보통 같으면 값을 사용하겠지만 이 문제에서는 인덱스를 사용해주어야한다. 몇초 뒤에 떨어지는지를 판단해야하기 때문이다. 따라서 값이 만족한다면 인덱스 스택에서 현재의 위치를 빼준다. 이때 0 -> 1로 갔을 때도 1초로 판단을 하기 때문에 스택에서 빼온 값에서 자신의 위치를 빼주면 원하는 값이 저장된다.
만일 스택이 비어있다면 마지막 인덱스의 위치에서 빼주어야한다. 이유는 문제 입출력 설명을 보면 마지막 인덱스의 위치에 있는 값은 0초 뒤에 떨어진다고 되어있다. 인덱스의 위치를 기준으로 판단을 하기 때문에 배열의 길이가 아닌 인덱스로 확인을 해줘야한다. 따라서 마지막 인덱스를 뜻하는 prices.length - 1에서 현재 위치를 빼주면 원하는 값이 저장이 된다.
마지막으로 비교를 다한 뒤 현재 위치의 값과 인덱스를 스택에 각각 저장해주고 반복문이 끝날 때까지 위의 과정을 반복해주면 문제가 해결된다!
만약 조금 더 자세한 설명을 보고 싶다면 아래 링크에 같은 방식으로 푼 다른 문제에 대한 블로그를 참고하길!
💡느낀 점
최근에 풀었던 문제 중 비슷한 방식으로 풀었던 문제가 있었다. 위의 문제를 보고 그 방식으로 풀어야겠다는 생각이 들었지만, 인덱스 관련해서 많은 고민을 했다. 하지만 너무 어렵게 생각하다가 많이 돌아가는 경우들이 생각나서 단순하게 하나의 스택을 더 만들어주자는 생각이 들었던 것 같다. 사실 문제를 해결하고도 좀 당황을 했지만 그만큼 내 실력이 늘었다는 반증이라고 생각하기로 했다!
링크
