monotonic stack

stack인데, 정렬된 스택을 말한다!

=> 위로 쌓는데, 정렬규칙을 만족 못하면 냅다 pop해버리기!

 

 

예를 들어,,,,, 

(bottom) [1, 2, 4, 5] (top) 이라는 스택이 있고, 이 스택의 규칙은 botom < top을 만족한다고 가정해보자

이 때 

3을 stack에 push하려고 한다!!! 그러면

    top쪽에 5 위에 쌓아버리면 규칙을 만족하지 못한다 pop

    top쪽에 4 위에 쌓아버리면 규칙을 만족하지 못한다 pop

    top쪽에 2 위에 쌓으면 규칙을 만족한다! push

=> (bottom) [1, 2, 3] (top) 이라는 스택으로 바뀌게 된다.

 

 

이런 스택의 장점은 뭐가있을까?? 특정 원소 기준으로 왼쪽이나 오른쪽에서 가장 가까운 큰값, 가장 가까운 작은값.. 같은 문제해결에 도움이 된다!

 

[1, 3, 2, 7, 5, 9, 6] 이라는 수열이 있다고 했을 때... 각 원소별로 오른쪽 중 가장 큰 값의 인덱스를 구하고 싶다.

이 문제의 경우,,,, (index가 0부터라고 생각하면)

[1, 3, 3, 5, 5, x, x] 이런 형태의 정답이 나오게된다!

 

이걸 완전탐색으로 풀면 어떻게 될까..? n + (n-1) + (n-2) ..... 번의 비교가 필요하므로 O(n^2)라는 시간복잡도를 가지게된다.

제곱이 들어가는 순간 시간복잡도가 아주아주 높은것이기 떄문에..... 다른 방법을 고안할 필요가 있다!

 

여기에 monotonic stack이 사용된다.

 

수열의 오른쪽부터 stack에 넣어주고,, index 정보를 같이 저장해보자

(stack의 top < bottom 규칙을 적용해보기!)

[1, 3, 2, 7, 5, 9, 6]

(6) : stack이 empty이므로 그냥 넣어준다

       index도 비어있으니까 그냥 넣어준다 (index!! 0부터 시작임)

       s : bottom [6] top

        i : [6]

(9) : stack에 있는게 더 작다! pop해주고 넣어준다

       9를 넣기 전에, monotonic stack은 비어있다 == 9보다 큰 수가 오른쪽에 없다는 뜻이므로

       index는 자기 자신이 된다

       s : bottom [9] top

        i : [6, 5]

(5) : stack에 쌓아줄 수 있다! (top < bottom규칙 ok)

       stack에 들어가 있는게 있다는건,,, 오른쪽에 (5)보다 큰 수가 있다는 뜻이다! 지금 top에 있는 아이의 index를 저장하자

       s : bottom [9, 5] top

        i : [6, 5, 5]

(7) : 앗! 지금 top (5)위에는 못쌓으니까 pop하는데, 새로운 top(9)위에는 쌓을 수 있다!

        index도 push하기 전 top (9)의 index를 이용한다

        s : bottom [9, 7] top

         i : [6, 5, 5, 5]

(2) : 그냥 쌓아줄 수 있다

        (7)의 index를 이용해준다

        s : bottom [9, 7, 2] top

         i : [6, 5, 5, 5, 3]

(3) : (2) pop한 다음 push한다

        push 직전의 top에 있는게 (7)이므로 (7)의 index를 이용한다

        s : bottom [9, 7, 3] top

         i : [6, 5, 5, 5, 3, 3]

(1) : 그냥 push!

        index도 (3)의 index를 사용한다

        s : bottom [9, 7, 3, 1] top

         i : [6, 5, 5, 5, 3, 3, 1]

=> i를 반대로 만들어주면... [1, 3, 3, 5, 5, 5, 6] 정답을 구할 수 있다!

 

=> 이렇게 되면, input배열을 한번만 순회하고 처리가 가능하다 == O(n)