두 줄 요약
각 element를 오름 차순, 내림 차순으로 유지하는 알고리즘 기법
배열에서 다음보다(순서 중요) 큰 element나 작은 element를 찾는 문제를 O(n) 이라는 시간에 효율적으로 해결할 수 있다.
즉,
1) 배열의 순서가 중요하고 (그 순서를 기점으로 계산해야 하기 때문에)
2) 어떤 기점에서 크거나 작은 요소를 찾아야 하는 문제
3) O(n^2)으로 해결할 수 없고, O(n)으로 해결해야 하는 경우
1) && 2) && 3) 의 해당하는 경우 Monotonic Stack을 사용하면 된다.
온도 문제로 생각해보는 Monotonic Stack의 필요성
각 일마다 온도를 순서대로 나타내어 temperatures 배열에 아래와 같이 저장했다고 하자.
temperatures = [73,74,75,71,69,72,76,73]
이제 각각의 날을 기준으로 몇 일 후에 따뜻해지는 날이 오는지 구하고 싶다.
예를 들면 첫 날에는 73도이고, 그 날보다 따뜻해지는 날은 바로 다음 날(74도) 이므로 1을 출력하고 싶다.
이때 어느 날도 당일 이후로 따뜻해지는 날이 없다면 0을 출력하고 싶다.
answer = [1,1,4,2,1,1,0,0]
이 문제를 해결하려면 모든 배열의 요소를 한 번씩 순회해보면서 답을 찾을 수 있다.
예를 들어 73도 일 때, 다음 날의 온도를 확인해서 73도 보다 크면 74도인 날 - 73도인 날을 구하면 된다.
이런식으로 N개에 대해서 약 N번 순회하면 O(n^2)의 시간복잡도로 답을 구할 수 있다.
그런데 만약에 주어진 temperatures의 데이터 값이 10^5 개 이고 제한 시간이 1초라면 O(n^2)으로 해결할 수 있을까?
보통 컴퓨터는 10^8을 연산하는데 1초가 걸리므로 시간 초과가 날 것이다.
그러면 O(nlogn) 이나 O(n)으로 해결해야 한다.
O(nlogn)은 정렬 알고리즘인데, 정렬을 해버리면 각 날의 각 데이터 온도 정보가 소실되어 버린다.
첫째 날의 온도가 73도가 아니라 정렬을 하면 첫째 날은 69도가 되어버리기 때문이다.
이때 O(n)으로 해결하는 방법으로 Monotonic Stack을 사용할 수 있다.
Monotonic Stack
스택에 저장되는 것을 오름차순 / 내림차순 순으로 유지되도록 한다.
예시를 들기 위해 내림차순으로 유지되도록 해보자.
1) 만약 스택이 비지 않았다면, (스택의 peek()로 본 그 날의 온도 < 현재 날의 온도) 이면 반복하여 pop을 한다. 그리고 해당 날부터 시작해서 최초로 기온이 해당 날보다 높은 날을 발견했으므로 answer 배열에 정답을 작성한다.
2) 순회하면서 그 날을 push한다.
위 이미지와 같이 온도가 75인 둘쨋날은 스택의 peek()인 첫째 날보다 온도가 더 높다. 따라서 pop()을 진행한다.
그리고 현재 day와 스택에 저장된 peek()을 빼면 day가 1인 날 이후로부터 최초로 기온이 높아지는 시점을 구한다. (day-stack.peek())
마찬가지로 0일차(73도)의 온도도 2일차(75도)의 온도보다 작으므로 pop()을 하고 answer 배열에 0일차 이후로 최초로 73도보다 높아지는 시점을 answer 배열에 기록한다. (day - stack.peek())
그리고 스택이 비었으므로 현재 날을 push 한다.
75보다 71이 더 작으므로 push() 한다.
마찬가지로 71보다 69가 더 작으므로 push() 한다.
이 과정을 코드로 작성하면 아래 코드와 같다.
import java.util.*;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] answer = new int[temperatures.length];
Deque<Integer> s = new ArrayDeque<>(); // Monotonic Stack
for(int day=0; day<temperatures.length; day++) {
while(!s.isEmpty() && temperatures[s.peek()] < temperatures[day]) { // 이전의 온도보다 현재 온도가 더 큰 경우 -> 각각의 해당 지점에서 더 큰 온도인 시점을 찾은 경우
answer[s.peek()] = day - s.peek();
s.pop();
}
s.push(day);
}
return answer;
}
}
