[스택] Monotonic Stack

👉 Monotonic Stack 이란? 

: 스택의 원소들을 오름차순 혹은 내림차순 상태로 유지하도록 하는 알고리즘

 

단조(monotonic)는 수학 함수에 사용되는 용어이다.

함수 y = f(x)가 다음 조건을 따를 때 단조 증가 또는 단조 감소하는 것으로 간주됩니다

x가 증가함에 따라 y도 항상 증가 -> 단조 증가 함수 

x가 증가함에 따라 y가 항상 감소 -> 단조 감소 함수 

 

☑️ 2가지 상황에 사용 가능 

-> 1) 배열 특정 위치에서 정렬된 숫자들만 보고 싶을 때 

-> 2) 배열 특정 위치에서 바로 다음 큰 값(or 작은 값)을 보고 싶을 때 

 

만약 브루트포스로 한다면 O(N^2)이 될 것이다. 하지만 모노토닉 스택을 사용한다면 O(N)으로 시간복잡도를 줄일 수 있다! 

 

👉 종류 

1) Increasing

stack의 상태를 "오름차순"으로 유지하기 위해(혹은, top의 값이 가장 큰 값이 되기 위해)

-> 삽입하려는 값보다 큰 값들은 모두 Stack에서 제거(pop)하고 값을 삽입한다. 

이때, 제거할 때 stack의 top값이 삽입하려는 값보다 작을 때까지 반복하면서 top값을 제거 후 값을 삽입한다. 

 

[ 예시 ]

현재 스택에 아래와 같이 1, 3,4 가 있다고 하자 그리고 이제 "2"을 삽입하려고 한다. 

1

3

4

 

 

😱😱😱😱 만약 바로 삽입을 하면 다음과 같이 스택의 정렬이 깨지게 될 것이다. 😱😱😱😱😱

1

3

4

2

 

 

 

하지만 3을 삽입하기 전에 스택의 TOP값이 2보다 크면 제거(pop)하고 3을 넣는다. 이 과정을 TOP이 2보다 작을 때가지 반복한다. 

 

예시에서 top값은 4인데 삽입하려는 값인 2보다 크므로 정렬을 유지하기 위해 4를 pop한다. 

1

3

 

또 top값은 3인데 삽입하려는 값은 2보다 크므로 정렬을 유지하기 위해 3을 pop한다. 

1

 

이제 top값인 1이 삽입하려는 값 2보다 작으므로 2를 삽입해도 stack의 정렬 상태가 유지되므로 2를 push한다. 

1

2

 

2) Decreasing

stack의 상태를 "내림차순"으로 유지하기 위해 (혹은, top의 값이 가장 작은 값이 되기 위해)

-> 삽입하려는 값보다 작은 값들은 모두 Stack에서 제거(pop)하고 값을 삽입한다. 

이때, 제거할 때 stack의 top값이 삽입하려는 값보다 클 때까지 반복하면서 top값을 제거 후 값을 삽입한다. 

 

 

문제

1) 옥상정원꾸미기 문제 

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

이 문제는 빌딩들이 한 줄로 나열되어 있고 각 빌딩은 자기 위치에서 오른쪽으로 "자기보다 작은 빌딩의 옥상"을 볼 수 있다. 

-> 각 빌딩마다 볼 수 있는 빌딩의 개수를 구하고 전체 합을 구하는 문제 

 

처음에는 2중 for문으로(브루트포스) "해당 빌딩이 볼 수 있는 빌딩들"을 조건으로 카운트 하려고 했다. 하지만 시간초과가 나기 때문에 다른 알고리즘을 고민했다. 

 

O(N^2)을 줄이기 위해서 "관점을 바꿔보자" 

N^2가 나오는 것은 문제 그대로 빌딩을 기준으로 다른 빌딩을 다 비교하려고 했기 때문이다. 

반대로 "내가 볼 수 있는 것" 에서 "내가 보이는가"로 바꾸고 "Monotonic stack"으로 스택을 사용하여 시간복잡도를 줄일 수 있다. 

이때, 해당 기준 빌딩(내가 보이는가에서 "내가"를 담당하는 빌딩, 스택에 넣을 빌딩)을 기준으로 내림차순으로 정렬되어 있어야 기준 빌딩이 보인다. 만약 중간에 불쑥 큰 빌딩이 있다면 가로막혀 빌딩이 보이지 않을 것이다. 

 

그리고 내림차순이 유지되도록 비교대상 빌딩보다 스택의 top이 작은 빌딩이 있다면 스택에서 제거하는 것을 반복하자 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class 옥상정원꾸미기 {
    public static void main(String[] args) throws Exception{
        new 옥상정원꾸미기().solution();
    }

    int[] buildings;
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int total = Integer.parseInt(br.readLine());
        buildings = new int[total];
        for(int i = 0 ; i < total; i++){
            buildings[i] = Integer.parseInt(br.readLine());
        }
        long result = 0;
        Deque<Integer> stack = new ArrayDeque<>();

        for(int i =0; i < buildings.length;i++){ // 빌딩 하나씩 검사 대상이 된다.
            while(!stack.isEmpty() && buildings[i]>=  stack.peek()){ // 뒤로 가면서 비교(들어있는 최신 값 순서대로)
                stack.pop(); // 해당 빌딩 기준으로 크기가 작거나 같다면 1) 지금 비교 대상 빌딩이 볼 수 없으며 + 2) 앞에 있는 빌딩들을 볼 수 없다(즉 앞에 등장할 빌딩들이 자기가 보이는지 비교할 때 지금 기준이 되는 빌딩이 더 커서 가려지기 때문에 보이지 않는 빌딩임)
            }
            result += stack.size(); // stack에 남아있는 것들은 다른 빌딩들을 볼 수 있는 빌딩들임
            stack.push(buildings[i]); // 지금 비교했던 빌딩 추가
        }
        System.out.print(result);
    }
}