모노톤스택(단조스택)☰

▶ 유형

• 모노톤 스택은 스택의 요소들이 항상 단조 증가하거나 단조 감소하도록 유지되는 특별한 형태의 자료구조다. 그래서 단조 스택이라고도 한다.
• 모노톤 스택의 가장 큰 장점은 특정한 패턴을 가진 다음/이전 원소를 찾는 문제를 선형 시간에 해결할 수 있다는 점인데, 각 원소는 최대 한 번씩만 스택에 들어가고 나오기 때문에 O(n^2)이 될 코드가 O(n)으로 유지된다., 이게 엄청 큰 장점이다.
• 배열에서 각 원소의 다음으로 큰 수 찾기, 히스토그램에서 가장 큰 직사각형 넓이 구하기, 온도가 더 높아지는 날까지 기다려야 하는 일수 계산하기 같은 유형에 적용할 수 있다.

flowchart TD
    Start([시작]) --> Init[스택 초기화]
    Init --> InputCheck{새로운 원소가<br>있는가?}
    
    InputCheck -->|Yes| StackEmpty{스택이<br>비어있는가?}
    InputCheck -->|No| End([종료])
    
    StackEmpty -->|Yes| PushElement[스택에 원소 추가]
    StackEmpty -->|No| CompareTop{스택 top과 비교}
    
    CompareTop -->|조건 위배| PopElement[스택에서<br>top 원소 제거]
    CompareTop -->|조건 만족| PushElement
    
    PopElement --> ProcessPopped[제거된 원소로<br>결과값 계산]
    ProcessPopped --> CompareTop
    
    PushElement --> InputCheck

▶ 전략

오름차순이면 들어가려는 수가 top 보다 작거나 같은 경우 pop을 반복하고 내림차순이면 들어가려는 수가 top 보다 크거나 같은 경우 pop을 반복하면 구현된다.

[2, 1, 4, 3, 5]를 예로 들어보겠다.

먼저 2가 들어온다. 그 다음 1이 들어오는데, 1은 2보다 작으므로 2를 pop하고 1을 push한다. push 전에 top과 비교하는 게 핵심이다.

 

4는 1보다 크므로 그대로 push하고, 3이 들어와야되는데 3은 4보다 작으니까 4을 pop 하고 3을 push한다. 이런식으로 진행이 되는데, 만약 입력 배열이 [2, 3, 5, 1] 이라면 어떻게 될까?

 

5까지 담았을 때 1과 비교하면 5가 pop되야한다. 여전히 top이 1보다 크므로 3도 pop, 2도 pop하면 스택이 빈 상태로 1이 push 되는 것이다.

 

즉 스택에 어떤 값을 넣기 전에 k 이상의 수를 모두 제거하고 k를 넣는 것이다.

 

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

얘를 한번 풀어보자.

for (int i = 1; i <= n; i++) {
    // 현재 막대(arr[i])보다 큰 높이의 막대들을 처리
    while (!st1.isEmpty()) {
        if (st1.peek() > arr[i]) {
            long nowVal = st1.pop();     // 현재 처리할 높이
            st2.pop();                   // 해당 높이의 위치도 함께 제거
  
            // 직사각형의 왼쪽 경계 찾기
            int leftIdx = -1;
            if (st2.isEmpty())
                leftIdx = 1;             // 스택이 비었다면 처음부터
            else
                leftIdx = st2.peek() + 1; // 이전 막대 다음 위치부터
            
            // 직사각형의 오른쪽 경계는 현재 위치 직전까지
            int rightIdx = i - 1;
            
            // 넓이 계산
            long width = rightIdx - leftIdx + 1;
            long area = width * nowVal;
            
            max = Math.max(max, area);
        } else {
            break;  // 현재 막대보다 작거나 같은 높이를 만나면 중단
        }
    }
    
    // 현재 막대의 정보를 스택에 추가
    st1.push(arr[i]);
    st2.push(i);
}

메인 로직이다.

입력 값과 top을 비교하는데, top이 더 크면 pop하고, idx를 들고있던 스택도 pop한다.(동기화)

지금 스택에 들어있는 값이 직사각형의 높이가 될 것이고, 인덱스의 차이만큼이 너비가 되는 것이다.

 

그래서 pop되는 시점의 바로 이전 인덱스가 top이 유지되고있는 인덱스이기 때문에 그걸 너비로 계산하면 끝난다. 물론 이 작업 후에, 아직 스택이 비어있지 않을 수 있기 때문에 스택을 비워주는 작업도 필수다. 근데 이미 탐색을 모두 한 시점이기 때문에, 오른쪽 끝을 n으로 잡고 시작한다.

// 남은 스택 정리
while (!st1.isEmpty()) {
    Long nowVal = st1.pop();
    st2.pop();
    int rightIdx = n; // 오른쪽 끝
    int leftIdx = -1;
    if (st2.isEmpty()) {
        leftIdx = 1;
    } else {
        leftIdx = st2.peek() + 1;
    }
    long width = rightIdx - leftIdx + 1;
    long area = width * nowVal;
    max = Math.max(max, area);
}

 

이 문제는 단조 증가로 해결했지만, 어떻게 문제에서 단조 증가, 감소를 파악할 수 있을까?

단조증가와 단조감소를 구분하는 핵심은 "요구사항"에 달려있다.
먼저 결과값의 조건을 파악해야한다. 찾는 값이 "더 큰 수"인지 "더 작은 수" 인지 구분해야된다.

• "더 큰 수"를 찾는 경우 → 단조감소 스택 유지
• "더 작은 수"를 찾는 경우 → 단조증가 스택 유지

이렇게 나눌 수 있는데,

https://www.acmicpc.net/problem/2493 
탑 문제를 보면, 이전 스택에 더 큰 수가 수신 기둥이다. 그래서 단조감소 스택을 유지하는 것이다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static int[] input;
    public static ArrayDeque<Integer> stack;
    public static ArrayDeque<Integer> idx; // idx
    public static int n;
    public static int[] res;

    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        input = new int[n + 1];
        res = new int[n + 1]; // idx 번 기둥이 수신했음을 기록하려고
        // idx 계산 1부터
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        // 입력 끝
        stack = new ArrayDeque<>();
        idx = new ArrayDeque<>();
        go();
        for (int i=1; i<=n; i++){
            sb.append(res[i]).append(" ");
        }
        System.out.println(sb);
    }

    public static void go() {
        for (int i = 1; i <= n; i++) {
            // 단조 감소 스택으로 가면 될 것 같다.
            int now = input[i];
            while (!stack.isEmpty()) {
                if (stack.peek() < now) { // top이 더 작으면 빼야된다
                    stack.pop();
                    idx.pop();
                } else {
                    // 그게 아니라면 수신한 것
                    res[i] = idx.peek();
                    break;
                }
            }
            stack.push(now);
            idx.push(i);
        }
    }
}

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!