모노토닉 스택(monotonic stack) 개념, 작동원리 + 예제 문제들 (주식 가격, 탑, 히스토그램에서 가장 큰 직사각형 찾기)

1. 모노토닉 스택이란?

모노토닉 스택 개념

모노토닉 스택(Monotonic Stack)은 원소들이 단조 증가하거나 단조 감소하는 순서를 유지하는 스택이다. 즉, 스택에 삽입되는 값들이 항상 특정한 순서를 따른다. 예를 들어, 단조 증가 스택은 스택에 있는 값들이 항상 오름차순(increasing)을 유지하도록 구성되며, 단조 감소 스택은 스택의 값들이 내림차순(decreasing)을 유지한다. 이 스택의 중요한 점은 특정 규칙을 만족시키기 위해 스택에서 값을 꺼내면서 문제를 해결한다는 점이다.

 

모노토닉 스택의 핵심은 배열을 한 번만 순회하면서 각 요소에 대해 문제의 요구 사항을 만족시키는 연산을 할 수 있다는 것이다. 이때 요구 사항은 일반적으로 다음 큰 수, 이전 작은 수 등을 찾는 데 사용된다. 이 과정에서 스택에 삽입된 값들은 필요할 때 제거되며, 각 값은 최대 한 번 삽입되고 한 번 제거되므로 시간 복잡도를 O(n) 로 풀 수 있다. 만약 각 요소에 대해 배열의 남은 요소들을 모두 비교하는 방식, 즉 브루트포스 방식의 연산에서는 O(n²) 시간이 걸릴 것이다. 모노토닉 스택을 사용하면 각 요소가 스택에 한 번 삽입되고 한 번 제거될 것이므로 시간 복잡도를 효율적으로 사용할 수 있다.

 

모노토닉 스택은 두 가지 특성으로 분류해볼 수 있다.

• 증가 스택 (Monotonic Increasing Stack): 스택 안에 들어가는 값들이 오름차순을 유지한다. 즉, 새 값이 스택의 맨 위에 있는 값보다 작으면 그 값이 스택에서 제거된다.
• 감소 스택 (Monotonic Decreasing Stack): 스택 안에 들어가는 값들이 내림차순을 유지한다. 즉, 새 값이 스택의 맨 위에 있는 값보다 크면 그 값이 스택에서 제거된다.
  
  

작동 원리

먼저 간단한 배열을 예시로 단조 증가 스택(Monotonic Increasing Stack)의 작동원리를 살펴보자.

arr = [4, 2, 6, 1, 5]

이 배열에 대해 모노토닉 스택을 적용하는 과정은 다음과 같다.

1. 첫 번째 요소: 4

• 스택 상태: 빈 상태
• 연산: 스택이 비어 있으므로 4를 스택에 삽입한다.
• 스택: [4]

2. 두 번째 요소: 2

• 스택 상태: [4]
• 연산: 현재 스택의 맨 위 값 4가 현재 값 2보다 크므로 스택에서 4를 제거한다. 오름차순 스택이 되어야 하기 때문에 4가 존재하는 상태에서 2가 삽입되면 안되는 것이다. 이후 2를 스택에 삽입한다.
• 스택: [2]

3. 세 번째 요소: 6

• 스택 상태: [2]
• 연산: 현재 스택의 맨 위 값은 2이다. 이 값이 현재 값 6보다 작으므로 6을 삽입해도 오름차순이 깨지지 않는다. 따라서 스택에서 값을 제거하지 않고, 6을 스택에 삽입한다.
• 스택: [2, 6]

4. 네 번째 요소: 1

• 스택 상태: [2, 6]
• 연산: 2번 스텝에서와 같은 이유로 현재 스택의 맨 위 값 6이 현재 값 1보다 크므로 스택에서 6을 제거한다. 그다음으로 스택의 맨 위 값 2가 현재 값 1보다 크므로 2도 스택에서 제거한다. 이후 1을 스택에 삽입한다.
• 스택: [1]

5. 다섯 번째 요소: 5

• 스택 상태: [1]
• 연산: 현재 스택의 맨 위 값 1이 현재 값 5보다 작으므로 스택에서 값을 제거하지 않고, 5를 스택에 삽입한다.
• 스택: [1, 5]

결론적으로 최종 스택 상태는 다음과 같이 된다.

 

[1, 5]

위의 예시를 살펴보면 단조 증가 스택은 값이 들어올 때마다 현재 스택의 맨 위 값과 비교하여, 스택의 정렬된 상태(오름차순)를 유지하려고 하는 것이 핵심이다. 만약 새로 들어오는 값이 스택의 맨 위 값보다 작다면, 그 값은 스택에서 제거되고 새로운 값이 추가된다.

알고리즘을 요약하자면 다음과 같다.

• 배열을 처음부터 끝까지 순회하며, 각 요소가 스택에 추가될 때 스택 맨 위 값과 비교한다.
• 조건을 만족하지 않는 값들은 스택에서 제거되고, 새로운 값이 삽입된다.
• 스택에는 단조 증가(혹은 감소)하는 값들이 남게 되며, 이를 통해 효율적인 조건 판별이 가능하다.

import java.util.Stack;

public class MonotonicStackExample {

    public static void main(String[] args) {
        int[] arr = {4, 2, 6, 1, 5};
        monotonicIncreasingStack(arr);
    }

    public static void monotonicIncreasingStack(int[] arr) {
        Stack<Integer> stack = new Stack<>();

        for (int num : arr) {
            // 스택의 맨 위 값이 현재 값보다 크면, 오름차순 유지하기 위해 pop
            while (!stack.isEmpty() && stack.peek() > num) {
                System.out.println("스택에서 제거: " + stack.pop());
            }
            // 현재 값을 스택에 추가
            stack.push(num);
            System.out.println("현재 스택 상태: " + stack);
        }

        System.out.println("최종 스택 상태: " + stack);
    }
}

코드를 실제로 돌려보자.

 

 

 

 

예상한 결과가 나오는 것을 볼 수 있다.

2. 모노토닉 스택의 필요성

그렇다면 "이 스택을 어디에 쓸 수 있을까?" "모노토닉 스택을 왜 사용하는 것이 더 효율적인가?"

 

이 질문에 답하기 위해, 모노토닉 스택의 실질적인 필요성과 그 효율성을 살펴보자. 증가하는 모노토닉 스택을 사용해 풀 수 있는 대표적인 문제는 "다음 작은 수(Next Smaller Element)" 문제이다.

다음 작은 수 문제(Next Smaller Element)

문제: 배열에서 각 요소에 대해 자신보다 오른쪽에 있는 값 중 첫 번째로 작은 값을 찾아야 한다. 만약 그런 값이 없다면 -1을 반환한다.

arr = [4, 2, 6, 1, 5]

이 배열에서 각 요소의 다음 작은 수는 다음과 같다.

• 4의 다음 작은 수는 2
• 2의 다음 작은 수는 1
• 6의 다음 작은 수는 존재하지 않으므로 5
• 1의 다음 작은 수는 -1
• 5의 다음 작은 수는 존재하지 않으므로 -1

그렇다면 결과는 다음과 같이 나와야 한다.

결과:

[2, 1, 1, -1, -1]

브루트포스 방식 vs. 모노토닉 스택 방식

먼저, 이 문제를 풀기 위해 가장 직관적으로 떠오르는 방법은 브루트포스 방식이다. 즉, 각 요소에 대해 오른쪽에 있는 모든 요소를 하나씩 비교해, 첫 번째로 작은 값을 찾아낼 수 있다.

브루트포스 방식

public static int[] nextSmallerElementBruteForce(int[] arr) {
    int[] result = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        result[i] = -1;  // 초기 값은 -1로 설정
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                result[i] = arr[j];
                break;  // 첫 번째 wkrdms 값을 찾으면 반복 종료
            }
        }
    }

    return result;
}

• 시간 복잡도: 각 요소에 대해 나머지 모든 요소를 비교하므로 O(n²)이다.

모노토닉 스택을 이용한 해결

모노토닉 스택을 사용하면 배열을 한 번만 순회하면서 더 효율적으로 다음 큰 수 문제를 해결할 수 있다. 왜 그럴까?

 

이유는, 모노토닉 스택을 사용하면 불필요한 비교를 줄일 수 있기 때문이다. 브루트포스 방식에서는 각 요소마다 모든 나머지 요소와 비교해야 하지만, 모노토닉 스택은 배열을 한 번 순회하면서 각 값에 대해 필요한 값들만 남겨둔다.

 

여기서 필요한 값이란, 현재 요소보다 작거나, 다음 비교에서 의미 있는 값들을 말한다. 구체적으로, 단조 증가 스택의 경우, 현재 값보다 작은 값들만 스택에 남긴다. 다음 작은 수를 찾을 때, 현재 값보다 작은 값이 필요하기 때문이다. 스택에 남아 있는 값들은 항상 다음 작은 수로 사용될 수 있는 후보들만 남기기 때문에 불필요하게 큰 값은 모두 제거된다.

 

예를 들어, arr = [4, 2, 6, 1, 5]에서 6을 처리할 때를 생각해보자. 그 이후에 더 작은 값 1이 등장했을 경우, 6은 더 이상 유효하지 않기 때문에 스택에서 제거된다. 반대로, 1은 다음 비교에서 중요한 값이 되므로 스택에 남는다.

 

이 과정을 통해 스택은 항상 의미 있는 값들만 유지하고, 다음 작은 수를 빠르게 찾을 수 있게 돕는다. 즉, 더 이상 다음 작은 수를 찾는 데에 쓸모없는 값들은 스택에서 제거되고, 그로 인해 불필요한 비교가 줄어들어 효율적인 탐색이 가능해진다.

 

이 문제를 모노토닉 스택으로 구현한 코드는 다음과 같다.

import java.util.Stack;

public class MonotonicStackExample {

    public static int[] nextSmallerElementMonotonicStack(int[] arr) {
        int[] result = new int[arr.length];
        Stack<Integer> stack = new Stack<>();

        // 배열을 오른쪽에서 왼쪽으로 순회
        for (int i = arr.length - 1; i >= 0; i--) {
            // 스택의 맨 위 값이 현재 값보다 크거나 같으면 pop
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }

            // 스택이 비어 있으면 -1, 그렇지 않으면 스택의 맨 위 값이 다음 작은 수
            result[i] = stack.isEmpty() ? -1 : stack.peek();

            // 현재 값을 스택에 추가
            stack.push(arr[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 6, 1, 5};
        int[] result = nextSmallerElementMonotonicStack(arr);

        // 결과 출력
        for (int res : result) {
            System.out.print(res + " ");
        }
    }
}

배열의 끝에서부터 시작해서 순회하면서 현재 값보다 작은 값들을 스택에 남기고, 큰 값들은 제거한다. 다음 작은 수 결정 while문을 반복하면서 결정된다. 스택의 맨 위 값이 현재 요소의 다음 작은 수가 될 것이다. 만약 스택이 비어 있다면, 해당 요소보다 작은 값이 없다는 뜻이므로 -1을 결과로 저장한다.

이처럼 모노토닉 스택을 이용하면 배열을 한 번만 순회할 수 있어, O(n) 시간 복잡도로 브르투포스 방식 대비 훨씬 효율적으로 풀 수 있게 된다.

3. 모노토닉 스택을 사용하는 문제 예시

1) 프로그래머스 level 2 주식가격

첫 번째는 주식가격 문제이다. 이 문제는 가격이 떨어지지 않은 기간을 계산하는 문제다.

 

주어진 prices 배열은 초 단위로 기록된 주식의 가격을 나타낸다. 각 시점의 가격이 이후로 얼마 동안 유지되었는지를 계산하는 것이 목표이다. 예를 들어, 가격이 떨어지지 않은 기간을 계산하는 방식은 다음과 같다.

 

prices = [1, 2, 3, 2, 3]

이 경우, 각 시점의 주식 가격이 떨어지지 않은 기간은 다음과 같다.

• prices[0] = 1: 이후로 4초 동안 가격이 떨어지지 않음
• prices[1] = 2: 이후로 3초 동안 가격이 떨어지지 않음
• prices[2] = 3: 이후로 1초 동안 가격이 유지된 후 하락
• prices[3] = 2: 이후로 1초 동안 가격이 유지된 후 하락
• prices[4] = 3: 마지막이므로, 가격이 유지된 기간은 0초

결과:

[4, 3, 1, 1, 0]

 

단조 감소 스택을 사용해 해결할 수 있다. 배열을 한 번만 순회하면서 현재 시점의 가격이 떨어지는 순간을 모노토닉 스택을 통해 처리하게 된다.

 

핵심 아이디어는 다음과 같다.

• 스택에는 인덱스를 저장한다. 배열을 순회하면서, 현재 가격이 이전 가격보다 낮아지는 시점이 발생하면 스택에서 인덱스를 꺼내서 그 차이만큼 기간을 계산한다.
• 스택에 있는 인덱스들은 항상 가격이 떨어지지 않은 상태를 유지하고 있다. 만약 가격이 떨어지면 스택의 값을 꺼내서, 가격이 유지된 시간을 기록한다.

사실, 이 문제는 위에서 다룬 다음 작은 수 문제와 구조가 매우 유사하다. 두 문제 모두에서, 핵심은 현재 값보다 작은 값(혹은 떨어지는 값)을 찾아 기간 또는 값을 계산하는 것이다.

 

다만, 다음 작은 수 문제에서는 작은 수를 찾는 것이 목적이라면, 주식 가격 문제에서는 가격이 유지된 기간을 구하는 것이 목적이다.

 

구현 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        Stack<Integer> 스택 = new Stack<>();

        // 주식 가격을 정방향으로 순회
        for (int i = 0; i < n; i++) {
            while (스택이비어있지않음(스택) && 가격이떨어짐(prices, i, 스택)) {
                int topIndex = 스택.pop();
                answer[topIndex] = 가격이떨어진시간을계산(i, topIndex);
            }
            스택.push(i);
        }

        // 끝까지 남아 있으면 끝까지 떨어지지 않은 것
        while (스택이비어있지않음(스택)) {
            int topIndex = 스택.pop();
            answer[topIndex] = 가격이떨어진시간을계산(n, topIndex+1);
        }

        return answer;
    }

    /**
     * <p>
     * 스택에서 꺼낸 인덱스와 현재 인덱스 간의 차이를 계산하여 가격이 유지된 시간을 반환합니다.
     * </p>
     * @param 현재인덱스 현재 시점의 인덱스 (i)
     * @param topIndex 스택에서 꺼낸 인덱스
     * @return 가격이 유지된 시간 (i - topIndex)
     */
    private static int 가격이떨어진시간을계산(int 현재인덱스, int topIndex) {
        return 현재인덱스 - topIndex; // 가격이 유지된 시간 계산
    }

    private static boolean 가격이떨어짐(int[] prices, int i, Stack<Integer> 스택) {
        return prices[i] < prices[스택.peek()];
    }

    private static boolean 스택이비어있지않음(Stack<Integer> 스택) {
        return !스택.isEmpty();
    }
}

2) 백준 gold 5 탑

또 다른 문제는 백준의 탑 문제이다. 탑 문제(BOJ 2493)는 탑들의 높이를 이용해 자신보다 높은 탑을 찾는 문제다.

 

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

 

N개의 탑이 직선으로 배열되어 있으며, 각 탑은 자신의 왼쪽에 있는 탑 중에서 자신보다 높거나 같은 첫 번째 탑에서 신호를 수신하게 된다. 즉, 탑은 자신보다 왼쪽에 있는 탑들 중에서 가장 가까이 있는 높은 탑을 찾아야 힌다.

 

탑이 다음과 같이 배열되어 있다고 가정할 때,

heights = [6, 9, 5, 7, 4]

이때 각 탑에서 신호를 받을 수 있는 탑은 다음과 같다.

 

• heights[0] = 6: 왼쪽에 탑이 없으므로 수신하는 탑이 없다 (출력: 0).
• heights[1] = 9: 왼쪽의 탑 6보다 크므로 수신하는 탑이 없다 (출력: 0).
• heights[2] = 5: 왼쪽의 탑 9이 더 크므로 탑 9에서 신호를 수신한다 (출력: 2).
• heights[3] = 7: 왼쪽의 탑 9이 더 크므로 탑 9에서 신호를 수신한다 (출력: 2).
• heights[4] = 4: 왼쪽의 탑 7이 더 크므로 탑 7에서 신호를 수신한다 (출력: 4).

결과:

[0, 0, 2, 2, 4]

 

주식가격 문제와는 유사하면서도 다른 부분이 있다.

 

두 문제 모두 모노토닉 스택을 사용하여 왼쪽 또는 오른쪽에서 조건을 만족하는 값을 찾는 것이 핵심이다. 두 문제 모두 불필요한 값(자신보다 작은 탑 또는 가격)을 제거하고, 남은 값들로부터 원하는 결과를 도출하는 방식으로 O(n) 시간 복잡도를 달성할 수 있다. 다만 목적에 있어서 다음과 같이 다르다.

• 탑 문제: 왼쪽에 있는 자신보다 높은 탑을 찾는 문제.
• 주식 가격 문제: 오른쪽에서 가격이 떨어지는 시점을 찾는 문제.

탑의 경우는 탑의 신호를 왼쪽으로 발사하여 첫 번째로 수신할 수 있는 탑을 찾아야 하기 때문이다.

문제를 모노토닉 스택으로 해결하는 이유

탑의 개수가 최대 50만 개로 주어지기 때문에, 브루트포스 방식으로 각 탑에 대해 왼쪽의 모든 탑을 탐색하면 시간 복잡도가 O(n²)가 되어, 매우 비효율적이다. 모노토닉 스택을 사용하여 O(n) 으로 풀어야 한다.

핵심 로직은 다음과 같다.

1. 스택을 사용하여 왼쪽에 있는 자신보다 작은 탑을 모두 제거한다. 이는 스택에 있는 탑 중 현재 탑보다 작은 값들은 의미가 없기 때문이다.
2. 현재 탑보다 큰 첫 번째 탑을 만나면, 그 탑이 신호를 수신할 수 있는 탑이 된다.

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] heights = new int[N];
        int[] result = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Tower> stack = new Stack<>();

        for (int i = 0; i < N; i++) {
            // 현재 탑보다 작은 탑은 모두 스택에서 제거
            while (!stack.isEmpty() && stack.peek().height < heights[i]) {
                stack.pop();
            }

            // 스택이 비어 있으면 수신할 탑이 없음
            if (stack.isEmpty()) {
                result[i] = 0;
            } else {
                // 스택의 맨 위에 있는 탑이 신호를 수신
                result[i] = stack.peek().index + 1;
            }

            // 현재 탑을 스택에 추가
            stack.push(new Tower(heights[i], i));
        }

        StringBuilder sb = new StringBuilder();
        for (int r : result) {
            sb.append(r).append(" ");
        }
        System.out.println(sb.toString());
    }

    static class Tower {
        int height;
        int index;

        Tower(int height, int index) {
            this.height = height;
            this.index = index;
        }
    }
}

3) 백준 platinum 5 히스토그램에서 가장 큰 직사각형 찾기

마지막으로 살펴볼 문제는 히스토그램에서 가장 큰 직사각형 찾기 문제(BOJ 6549)이다. 이 문제는 히스토그램 막대들의 높이를 이용해 가장 큰 직사각형의 넓이를 찾는 문제이다.

 

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

 

주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 것이 목표이다. 각 직사각형의 너비는 1로 동일하지만, 높이는 다를 수 있다. 예를 들어, 히스토그램이 아래와 같이 주어진다고 가정해보자.

heights = [2, 1, 4, 5, 1, 3, 3]

이 히스토그램에서 가장 큰 직사각형의 넓이는 다음과 같다.

• 높이 5인 직사각형에서 좌우로 확장한 최대 넓이 = 5 (넓이: 1x5 = 5)
• 높이 4인 직사각형에서 좌우로 확장한 최대 넓이 = 8 (넓이: 2x4 = 8)
• 가장 큰 넓이는 8이다.

결과:

8

마찬가지로 이 문제 역시, 브루트포스로 풀면 각 직사각형마다 좌우로 확장할 수 있는 범위를 계산해야 하므로 O(n²)의 시간이 걸리게 된다. 하지만, 스택을 사용하면 O(n) 시간 복잡도로 문제를 해결할 수 있다.

 

모노토닉 스택을 사용한 해결 방법

스택을 사용하여 높이가 낮아지는 순간 직사각형의 넓이를 계산하는 것이 핵심 아이디어이다. 스택은 히스토그램의 오름차순 높이를 유지한다. 만약, 현재 막대가 스택의 top에 있는 막대보다 낮다면, 스택에서 값을 꺼내고 이전에 쌓여있던 직사각형의 최대 넓이를 계산한다.

핵심 로직은 다음과 같다.

1. 스택에 직사각형의 인덱스를 저장한다. 히스토그램을 차례대로 스캔하면서 오름차순 높이를 유지하도록 스택에 저장힌다.
2. 현재 직사각형의 높이가 스택의 top 값보다 작아지면, 스택에서 pop하여 직사각형을 계산하고 최대 넓이를 갱신한다.
3. 모든 직사각형을 스캔한 후에도 스택에 남은 값들이 있을 수 있기 때문에, 스택에 남은 직사각형들에 대해서도 넓이를 계산해준다.

구현 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            String[] input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);

            if (n == 0) break;

            int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
                heights[i] = Integer.parseInt(input[i + 1]);
            }

            System.out.println(getMaxRectangleArea(heights));
        }
    }

    public static long getMaxRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        int n = heights.length;

        for (int i = 0; i < n; i++) {
            // 스택이 비어있지 않으며 현재 막대의 높이가 스택의 top보다 작으면 pop
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }

        // 남은 스택 처리
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, (long) height * width);
        }

        return maxArea;
    }
}

 

백준의 탑 문제와 유사하게, 스택을 사용하여 불필요한 값(작은 값)을 제거하고 필요한 값만 남긴 채 문제를 풀 수 있다. 탑 문제에서는 왼쪽에서 높은 탑을 찾았다면, 히스토그램 문제에서는 넓이를 계산하는 데 활용된다.

 

이 문제에 대한 보다 자세한 풀이는 다음 글에서도 볼 수 있다. 

 

[백준] 히스토그램에서 가장 큰 직사각형 (자바 풀이)