Stack의 활용에서 자주 나오는 구조이다. Stack을 활용하는 대표적인 예시 중에 하나라서, Code Interview때 물어볼 수도 있다. Stack은 함수 Call에도 사용하고, ISR(Interupt Service Routine)에서도 사용되는데, 코딩 테스트에는 Monotone Stack이 자주 나오는거 같다.
개념
개념은 Monotone Stack의 이름에서 뜻을 알 수 있는데, Monotone(수학에서 나온 단어이다. 단조증가, 단조감소와 같이 우상향, 우하양을 이야기한다) 상태를 stack에 유지시켜주자는 이야기이다. Stk = [4,3,2,1] 과 같이 스택 내를 정렬된 상태를 유지시켜주자는 이야기이다.
활용 (Use Case)
Monotone Stack는 NGE(Next Greater Element) , PGE(Previous Greater Element)와 같은 문제를 해결할 수 있다고 알려져있다.
NGE(Next Greater Element)
NGE는 막 거창한게 아니다. NGE는 각각의 원소에 대해서 다음으로 큰 원소가 언제 처음으로 등장하고 싶은지 알고 싶을 때 사용을 할 수 있다. 물론 , 이중반복을 이용해서 다음으로 큰 원소를 찾는건 어렵지 않고, 꽤 직관적인 방법이기 때문에 데이터 갯수가 작다면 매우 훌륭한 코드이다. 하지만, 데이터 갯수가 커서 O(N)을 요구하는 상황이라면 NGE를 구하는데 Monotone Stack을 이용할 수 있다.
예를들어, Arr=[4,7,10,5,6]이라고 하자. 내가 원하는 결과는 다음과 같다.
- 4의 NGE는 7이다.
- 7의 NGE는 10이다.
- 10의 NGE는 없기 때문에, -1이다.
- 5의 NGE는 6이다.
- 6의 NGE는 마지막 원소이기 때문에 없다. -1이다.
NGE = [7,10,-1,6,-1]
Stack을 이용해서 , 위를 어떻게 구할 수 있을까
바로, 스택을 내림차순으로 유지시켜주면 된다. 아래의 과정을 하나씩 보자. 과정의 핵심은 원소를 stack의 Top보다 작을 때까지 안의 원소를 pop하는거다. 이때, 인덱스를 기준으로 집어넣으면 더 쉽게 구현할 수 있다.
- 4의 인덱스('0') stack에 push한다.
- 4보다 7이 크기 때문에 4를 pop하고 7을 push한다.
- pop할 때, NGE[0]에 7이라는 값을 기록하게 됩니다.
- 7보다 10이 크기 때문에, 7를 pop하고 10을 push한다.
- pop할 때, NGE[1]에 10의 값을 기록하게 됩니다.
- 5는 10보다 작기 때문에, 넣어준다. stk=[2,3]
- 6은 5보다(stack의 top)보다 크기 때문에, 빼준다.
- pop할 때, NGE[3]에 6의 값을 기록해준다.
stack에 남아있는 값들로 NGE[i]에 각각 -1로 처리해주면 NGE배열이 완성된다.
Code
#include <bits/stdc++.h>
using namespace std;
int arr[6] = {4, 7, 10, 5, 6};
int NGE[6];
int main()
{
vector<int> stk;
for (int i = 0; i < 5; i++)
{
while (!stk.empty() && arr[stk.back()] < arr[i])
{
NGE[stk.back()] = arr[i];
stk.pop_back();
}
stk.push_back(i);
}
for (int c : stk)
{
NGE[c] = -1;
}
for (int i = 0; i < 5; i++)
{
cout << NGE[i] << ' ';
}
return 0;
}
배열을 뒤에서 부터 탐색해서 내림차순을 유지시키면 PGE를 구할 수 있다.
refer
https://www.youtube.com/watch?v=dtiBmmIPR0E&t=338s
https://www.youtube.com/watch?v=68a1Dc_qVq4&t=201s
