[자료구조] 모노톤 스택(Monotone stack)

1. 모노톤 스택(Monotone stack) 이란?

스택(Stack)은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 후입선출(LIFO:Last In, First Out) 형태의 자료구조 입니다.
즉, 가장 먼저 들어온 데이터가 가장 마지막에 나가고, 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.

 

• 모노톤 스택(Monotone stack)은 특정한 순서를 유지하면서 데이터를 관리하는 스택 자료구조 입니다.
  • Monotone은 증가하거나 감소하는 등의 일정한 경향이 보임을 의미합니다.
• 모노톤 스택(Monotone stack)은 증가하거나 감소하는 일정한 경향을 가진 스택입니다.
• 모노톤 스택(Monotone stack)은 특정 문제에 대해 시간 복잡도를 O(N)으로 줄여주는 매우 효율적인 해결책을 제공합니다.
  • 다음/이전 데이터의 최댓값/최솟값을(Nearest Greater/Smaller Element) 찾는 문제에 유용하게 쓰입니다.

 

2. 모노톤 스택(Monotone stack)의 종류 및 구현

스택은 LIFO(Last In, First Out) 자료 구조이기 때문에 모노톤 스택의 최상위 요소를 제거하면서 단조 증가/감소 순서를 유지합니다. 새로운 요소는 항상 최상위에 추가됩니다.

1) 단조 증가 스택(Monotone Increasing Stack)

• 스택의 요소들이 오름차순으로 정렬되는 스택
  • 오름차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 커진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 내려갈수록 값이 작아짐

10 (top)

5

2

1

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 크거나 같은 경우를 유지하는 스택
  
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 작거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 항상 특정 순서(오름차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

2) 단조 감소 스택(Monotone Decreasing Stack)

• 스택의 요소들이 내림차순으로 정렬되는 스택
  • 내림차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 작아진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 갈수록 값이 커짐

1 (top)

2

5

10

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 작거나 같은 경우를 유지하는 스택
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 크거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 특정 순서(내림차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 작거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() <= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 클 때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

 

 

3. 모노톤 스택(Monotone stack) 구현 - 예시로 확인

개인적으로 모노톤 스택의 종류에 대해 이해하는데에 조금 시간이 걸렸습니다. 단조 증가 스택과 단조 감소 스택의 정렬 순서가 어디부터 시작하는지에 대한 정확한 이해를 못하고 무작정 이해하려고 하다보니 헷갈렸습니다. 

그래서 마지막으로 배열 예시를 정리하면서 아직은 조금 헷갈리는 부분을 정리해보겠습니다.

public static void main(String[] args) {
    int[][] testArrays = {
        {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
        {10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
        {5, 5, 4, 4, 3, 3, 2, 2, 1, 1},
        {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}
    };

    for (int[] arr : testArrays) {
        System.out.println("Monotonic Stack for array: " + Arrays.toString(arr));
        incresing(arr);
        decresing(arr);
        System.out.println();
    }
}

테스트 배열을 위와 같이 4가지 정도로 생성해두고 단조 증가 스택과 단조 감소 스택을 출력해보았습니다.

*각 스택은 2번 목차의 코드를 수행해서 생성

 

위 코드에 대한 출력 결과는 아래와 같습니다.

Monotonic Stack for array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Monotonic Increasing Stack: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
Monotonic Decreasing Stack: 10, 

Monotonic Stack for array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 

Monotonic Stack for array: [3, 6, 1, 9, 4, 7, 2, 8, 5, 10]
Monotonic Increasing Stack: 10, 5, 2, 1, 
Monotonic Decreasing Stack: 10,

 

단조 증가 스택은 요소들이 오름차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

단조 감소 스택은 요소들이 내림차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

인 점을 머리속에 꼭 담아두고 출력 결과를 확인해보면, 제대로 출력되는 것을 알 수 있습니다.

 

코드 구현시 중복 값은 허용하지 않았기 때문에 3번 예시처럼 중복 값이 없는 것을 확인할 수 있습니다.

만약 중복을 허용한다면 아래와 같은 결과가 출력됩니다.

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 1, 
Monotonic Decreasing Stack: 1, 1, 2, 2, 3, 3, 4, 4, 5, 5,

 

단조 증가 스택 함수는 아래와 같을때 마지막 예시인 {3, 6, 1, 9, 4, 7, 2, 8, 5, 10} 에 대한 단조 증가 스택 생성 과정을 구체적으로 보겠습니다.

public static void incresing(int[] arr) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i=0; i<arr.length; i++) {
        // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
        while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
        	stack.removeFirst();
        }
        // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
        stack.offerFirst(arr[i]);
    }
}

 

• 배열: {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}

배열 요소	설명	스택
첫번째 요소: 3	스택이 비어있으므로 요소 3 추가	[3]
두번째 요소: 6	스택의 맨 위 요소(3)가 6보다 작으므로 6을 스택에 추가	[6, 3]
세번째 요소: 1	스택의 맨 위 요소(6)가 1보다 크므로, 6을 스택에서 제거	[3]
	스택의 맨 위 요소(3)가 1보다 크므로, 3을 스택에서 제거	[ ]
	스택이 비었으므로 요소 1 추가	[1]
네번째 요소: 9	스택의 맨 위 요소(1)가 9보다 작으므로, 9를 스택에 추가	[9, 1]
다섯번째 요소: 4	스택의 맨 위 요소(9)가 4보다 크므로, 9를 스택에서 제거	[1]
	스택의 맨 위 요소(1)가 4보다 작으므로, 4를 스택에 추가	[4, 1]
여섯번째 요소: 7	스택의 맨 위 요소(4)가 7보다 작으므로, 7을 스택에 추가	[7, 4, 1]
일곱번째 요소: 2	스택의 맨 위 요소(7)가 2보다 크므로, 7을 스택에서 제거	[4, 1]
	스택의 맨 위 요소(4)가 2보다 크므로, 4를 스택에서 제거	[1]
	스택의 맨 위 요소(1)가 2보다 작으므로, 2를 스택에 추가	[2, 1]
여덟번째 요소: 8	스택의 맨 위 요소(2)가 8보다 작으므로, 8을 스택에 추가	[8, 2, 1]
아홉번째 요소: 5	스택의 맨 위 요소(8)가 5보다 크므로, 8을 스택에서 제거	[2, 1]
	스택의 맨 위 요소(2)가 5보다 작으므로, 5를 스택에 추가	[5, 2, 1]
열번째 요소: 10	스택의 맨 위 요소(5)가 10보다 작으므로, 10을 스택에 추가	[10, 5, 2, 1]

 

최종적으로 스택을 출력하면 [10, 5, 2, 1] 이 출력됩니다.

스택의 맨 위 요소가 현재 배열 요소보다 크거나 같으면 스택에서 제거하고, 현재 요소를 스택에 추가하면서 단조성을 유지할 수 있는 것입니다.

 

4. 모노톤 스택(Monotone stack) 관련 문제

• 백준 - 탑 보기

[백준] 탑 보기 - 자바(Java)

 

 

참고 링크

모노톤 스택, 큐,덱에 관하여.