모노톤 스택

모노톤 스택에 대해서 알아봅니다.

오름, 내림 차순을 유지한 스택을 만듭니다.

아이디어

발상은 top에 있는 숫자와 새롭게 들어오는 숫자를 비교하고, 경우에 따라 pop 하며 진행합니다
- 중복없는 오름차순 인경우, 들어가려는 수가 top 보다 작거나 같은 경우 pop을 반복하면 구현 가능.
- 중복없는 내림차순 인경우, 들어가려는 수가 top 보다 크거나 같은 경우 pop을 반복하면 구현 가능
https://www.acmicpc.net/problem/11003 이문제를 O(NlogN)이 아닌, O(N)으로 푸는 아이디어를 생각하다가 알고리즘 명칭을 정확히 알게 되었다.
- 이전에 무의식적으로 사용하고 있던 테크닉이긴 한다.

stack에 넣는것을 {위치 인덱스, 숫자} 로 한다면?

1 3 2 5

다음과 같은 숫자가 들어간다고 해보자.
- 이중 N번 째 들어가는 숫자보다 왼쪽에 있으면서, 작은 첫번째 숫자를 찾는다고 해보자.
- N번쨰 숫자보다 왼쪽에 있는 작은 것을 구하니 오름차순으로 유지해야한다.

[ {0,1} ]
- 첫번째 숫자는 비교할게 없으므로 그냥 들어간다.
[ {0,1}, {1,3} ], 아직 {1,3} 는 들어간게 아니다.
- 3은 top {0,1} 에서 숫자인 1 보다 크다. 그러므로 별 이상없이 push가 가능하다.
- 그리고 1은 찾고 있는 정보인, 3보다 왼쪽에 있으면서 작은 첫번째 숫자를 찾는다고 해보자. 라는 조건에 만족한다.
- 즉 3보다 왼쪽에 있으면서 작은 첫번째 숫자의 위치는, top의 인덱스인 0 이 된다.
[ {0,1}, {1,3}, {2,2} ], 아직 {2,2} 는 들어간게 아니다.
- 2가 들어갈 경우, top인 3 보다 작으므로 오름차순을 깨게 된다.
- top을 pop한다.
  - [ {0,1}, {2,2} ], 아직 {2,2} 는 들어간게 아니다.
  - 이제 2는 top인 1 보다 크므로, push가 가능하다.
  - 그리고 찾고 있는 2보다 왼쪽에 있으면서, 작은 첫번째 숫자를 찾는다고 해보자. 라는 조건에 만족한다.
  - 즉 2보다 왼쪽에 있으면서 작은 첫번째 숫자의 위치는, top의 인덱스인 0 이 된다.
[ {0,1}, {2,2}, {3,5} ]
- 5는 2보다 크므로 push가 가능하다.
- 즉 5보다 왼쪽에 있으면서 작은 첫번째 숫자의 위치는, top의 인덱스인 2 가 된다.

스택안에, 어떤 정보를 어떻게 보관 하느냐에 따라서 다양한 정보를 얻을 수 있다.
핵심은 알고리즘 이름처럼 스택을 단조롭게 만드는 것이다.
- 오름, 내림 차순으로 유지한다.
- 이때 오름, 내림 차순으로 유지하는데 쓰이는 정보외에 다른 정보도 담는다면 다양하게 활용할 수 있게 된다.