Monotonic Stack, 단조 스택이란?

Monotonic Stack (단조 스택)

• Monotonic Stack은 원소가 Increasing / Decreasing으로 정렬되어 있는 배열을 의미한다.
• Monotonic Stack 그 자체로 유용함은 없지만, 정렬되어 있지 않은 배열을 Monotonic Stack으로 만드는 과정 혹은 Monotonic Stack에 새로운 원소가 입력되었을 때, 정렬하는 과정에서 발생하는 정보들이 유용하다.
• 이를 사용해 풀 수 있는 문제들이 있는데, 대표적인 문제는 Find Next Greatest Number 이다. Brute Force로도 풀 수 있지만 Time Complexity : O(n^2)이므로 입력 배열의 원소 개수가 많을 수록 불리하다. 이때 Monotonic Stack을 만드는 과정에서의 정보를 이용하면 Tme Complexity : O(n)으로 풀 수 있다.
• 예시 문제는 Leet Code의 739. Daily Temperatures (level : medium) 이다.

Monotonic Stack (단조 스택) 만드는 예시

Monotonic Stack에 새로운 원소를 추가하고, 정렬하는 과정을 보자.

Decreasing으로 정렬되어 있는 Stack에 '4'를 추가한다. 이때 Stack의 '3', '2'는 '4'보다 작다. Decreasing 속성을 유지하면서 새로운 원소 '4'를 추가하기 위해 '3', '2'는 Stack에서 POP 한다. 그리고 '4'를 추가한다. 그 결과 원소를 '8', '6', '4'를 가진 Stack이 만들어 진다.

Monotonic Stack에서 '4'보다 큰 값은 '6'이 된다. 이는 다시 말해, '4'의 Next Greatest Number은 '6'임을 의미한다. 이러한 특성을 이용해 Find Next Greatest Number 문제를 풀 수 있다.

Source Array : [8, 6, 3, 2]
Make Monotonic Decreasing Stack
Get Element 4
Monotonic Stack : [8, 6, 4]

Monotonic Stack을 사용한 문제 풀이 예시

LeetCode 739. Daily Temperatures 문제를 풀어보면 된다. 여기서는 간략화된 Find Next Greatest Number 문제를 풀어보겠다.

문제 : 다음 입력 배열이 있을 때, 0번째 원소부터 접근하며 
각 원소보다 큰 숫자가 몇번째 인덱스에 있는지 계산하라

Source Array : [4, 6, 8, 1, 2]

이 문제를 풀기 위해선 Monotonic Stack 배열, 인덱스를 저장할 배열 2개 변수가 필요하다.

먼저 입력된 배열을 Monotonic Stack으로 만드는 과정을 반복하고, 이때 도출되는 정보를 활용해 Next Greatest Number의 인덱스를 계산하면 된다.

 

Step 1. 입력 배열의 가장 마지막 원소인 '2'에 접근해 Monotonic Stack에 넣는다. Monotonic Stack의 원소 개수는 0이었으므로 그냥 Push해주면 된다. Index Array에는 Monotonic Stack에서 '2'의 왼쪽에 있는 원소의 인덱스를 저장하면 되나, 원소 개수가 없으므로 자신의 Index를 저장한다.

Source Array : [4, 6, 8, 1, 2]
                            ^ 접근
Monotonic Stack : [2]
Index Array : [4]

 

Step 2. 입력 배열의 마지막 2번째 원소인 '1'에 접근해 Monotonic Stack에 넣는다. Monotonic Stack에는 '2'만 있는데, 이는 '1'보다 크므로 그대로 둔다. 이때 Index Array에는 Monotonic Stack에서 '1'의 왼쪽에 저장된 '2'의 인덱스인 4를 저장해준다. (바로 이 과정에서 '1'원소의 Next Greatest Number가 '2'임을 알게 된다.)

Source Array : [4, 6, 8, 1, 2]
                         ^ 접근
Monotonic Stack : [2, 1]
Index Array : [4, 4]

 

Step 3. 입력 배열의 마지막에서 3번째 원소인 '8'에 접근해 Monotonic Stack에 넣는다. Monotonic Stack에는 '2'와 '1'이 있는데, 새로운 입력 원소 '8'이 가장 크다. 그래서 Monotonic Stack의 Decreasing 정렬 속성을 유지하기 위해 '2'와 '1'을 삭제하고 '8'을 넣는다. 이때 Monotonic Stack에는 '8' 왼쪽의 원소가 없으므로 Index Array에는 해당 원소의 인덱스인 2를 저장한다. ('8'의 경우 입력 배열에서 인덱스가 2이다. 그리고 Monotonic Stack에서 '8' 왼쪽의 값이 없다. 이는 Next Greatest Number가 없고 자신이 가장 큰 값임을 의미한다.)

Source Array : [4, 6, 8, 1, 2]
                      ^ 접근
Monotonic Stack : [8]
Index Array : [4, 4, 2]

 

Step 4.'6'에 접근해 Monotonic Stack에 넣는다. Step1, 2, 3에 명시한 알고리즘과 동일하게 처리하면 다음과 같다.

Source Array : [4, 6, 8, 1, 2]
                   ^ 접근
Monotonic Stack : [8, 6]
Index Array : [4, 4, 2, 2]

 

Step 5. 마지막으로 '4'에 접근해 위와 동일한 알고리즘으로 처리한다.

Source Array : [4, 6, 8, 1, 2]
                ^ 접근
Monotonic Stack : [8, 6, 4]
Index Array : [4, 4, 2, 2, 1]

 

이렇게 입력 배열로부터 Monotonic Stack을 완성했다. Monotonic Stack 그 자체로는 유용한 정보가 없다. 하지만 이를 만드는 과정에서 Index Array 값을 생성할 수 있었다. 이는 입력 배열의 각 원소보다 큰 원소가 몇번째 인덱스에 위치해 있는지 알려준다. 우선 입력 배열은 가장 마지막 원소부터 접근하여 처리했기 때문에 Index Array 값도 역전해준다.

Source Array : [4, 6, 8, 1, 2]
Index Array : [1, 2, 2, 4, 4]

 

이는 첫번째 원소인 '4'의 Next Greatest Number (이하 NGN)은 인덱스 1에 위치한 '6' 임을 말해준다. (Index Arrayp[0] = 1)

두번째 원소인 '6'의 NGN은 인덱스 2에 위치한 '8',

세번째 원소인 '8'의 NGN은 인덱스 2, 즉 자기자신이다. 다시말해 자신보다 큰 값이 없는 것이다.

네번째 원소인 '1'의 NGN은 인덱스 4인 '2'

마지막 원소는 당연히 NGN이 없다. 그래서 자기자신이다.

 

Monotonic Stack 개념을 정리하며

Monotonic Stack 자체로는 유용함이 없다. 하지만 입력 배열을 Monotonic Stack을 만드는 과정에서 배열 내 각 원소의 Next Greatest Number를 찾을 수 있다. (반대로 Next Smallest Number 도 찾을 수 있을 것이다.) 범용적인 문제풀이에 적용할 수 있는 알고리즘은 아니지만 위와 같은 문제에서는 Time Complexity : O(N)의 강력한 알고리즘이다.