모노토닉 스택 (Monotonic Stack)

  • 원소가 Increasing / Decreasing으로 정렬되어 있는 배열을 의미한다.
  • 정렬되어 있지 않은 배열을 Monotonic 하게 만들거나 Monotonic Stack에 새로운 원소가 입력되었을 때, 정렬하는 과정에서 발생하는 정보들이 유용하다.

 

추천 문제

 

17298번: 오큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

www.acmicpc.net

 

 

 

예시 문제 : 옥상 정원 꾸미기

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             =
 =           =
 =     -     =
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =
 =  =  =  =  =  =
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호
  • 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
  • 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
  • 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
  • 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
  • 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
  • 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

 

 

위 문제를 보면, 한 방향(오른쪽)으로 이동하면서 조건에 해당하는 값을 마주치면 필요한 처리를 해주면 된다.

  1. 한칸씩 움직이면서 Stack에 해당 (건물의 위치, 빌딩의 높이) 를 추가한다.
  2. Stack에 빌딩의 정보가 존재할 때, 현재 위치한 빌딩(N)과 스택에 마지막으로 들어간 빌딩(N-1)을 비교해 높이가 크거나 같으면 스택이 비워질 때 까지( 현재 위치의 빌딩보다 작은 크기의 빌딩이 없을 때 까지) 연산을 한다.
  3. res[스택에 있던 빌딩의 위치] 에 현재 위치한 빌딩의 위치 - 스택에 있던 빌딩의 위치 - 1 를 저장한다. -1을 해주는 이유는 현재 위치는 스택에서 꺼낸 빌딩이 확인할 수 없기 때문이다.
for i in range(len(arr)) :
    while stk and stk[-1][1] <= arr[i] :
        idx,val = stk.pop()
        res[idx] = i - idx - 1

    stk.append((i, arr[i]))

티스토리툴바