Monotone Stack

모노톤 스택

역할

• 스택을 오름차순 or 내림차순 등으로 정렬된 상태를 유지한다.
• 이를 이용해 임의의 위치 x보다 왼쪽에 있는 크거나 작은 수의 위치를 바로 알 수 있다.

알고리즘

• 스택에 들어갈 수를 모두 입력받는다. stack[i] = sc.nextInt()
• 스택에 수를 넣으면서 현재 스택에 자신보다 작은 수는 모두 제거한다. while(arr.size()!=0 && arr.peek()<=data) arr.pop();

예제 : 백준 6198

• 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, …. , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다. 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다. 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다. 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다. 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다. 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다. 따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.Scanner;
import java.util.Stack;


public class baek_6198 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> arr = new Stack<>();
        int[] dp = new int[n];
        long answer = 0;
        for(int i=0; i<n; i++){
            dp[i] = sc.nextInt();
        }
        for(int i=0; i<n; i++){
            int data = dp[i];
            while(arr.size()!=0 && arr.peek()<=data) arr.pop();
            answer+=arr.size();
            System.out.println(arr.size());
            arr.add(data);
        }
        System.out.println(answer);
    }
}