[BOJ 6198] 옥상 정원 꾸미기 - JAVA, Gold5

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

6198번: 옥상 정원 꾸미기

사용한 알고리즘: 모노톤 스택(Monotone Stack)

 

풀이전략

https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/

monotone stack

먼저 문제를 풀기위해서는 monotone stack이라는 스택을 활용한 알고리즘을 알고 있어야 한다.

 

문제 풀이 전략으로 가장 쉽게 접근할 수 있는 방법은

이중 반복문을 사용해 특정 빌딩이 오른쪽에 있으면서 옥상을 볼 수 있는 빌딩 개수를 일일이 세는 방법이다.

 

하지만 이 방법은 시간 복잡도가 O(N^2)으로

빌딩의 개수가 최대 80,000개가 가능하기 때문에

최악의 경우 필요한 연산이 80,000*80,000= 6,400,000,000(64억)이다.

JAVA는 초당 1억번 연산하기 때문에 최악의 경우 약 64초가 걸려 시간 초과가 발생한다.

 

그런데 monotone stack의 시간 복잡도는 O(N)으로 획기적으로 시간을 절약할 수 있다.

 

이 문제에서 가장 중요한 아이디어는 특정 빌딩이 볼 수 있는 다른 빌딩의 개수를 세는 것이 아니라,

특정 빌딩을 바라볼 수 있는 건물들의 개수를 세어야 한다는 발상이다.

 

위와 같은 전략을 세웠을 경우, 이를 효과적으로 구현해 낼 수 있는 알고리즘이 monotone stack이다.

 

아래 그림은 스택에 입력받은 빌딩의 높이를 차례로 넣되,

만약 입력하기 전의 빌딩들 중 입력한 빌딩보다 높이가 낮은 빌딩이 있으면 스택에서 모두 pop한다.

 

그러면 하나의 입력으로 발생하는 변화하는 스택의 크기가

해당 빌딩을 바라볼 수 있는 빌딩의 개수가 된다.

 

따라서 각 과정마다의 스택 크기를 모두 더한 값을 출력하면 정답이 도출된다.

 

1) Stack에 1번 빌딩 높이인 10을 삽입 - 스택 사이즈 0 ( 자신은 제외한 사이즈)

2) Stack에 2번 빌딩 높이인 3을 삽입 - 스택 사이즈 1 

    ...

6) Stack에 6번 빌딩 높이인 2를 삽입 - 스택 사이즈 1

 

제출코드

import java.io.*;
import java.util.Stack;

public class Main{
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

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

        Stack<Integer> stack = new Stack<>();
        long ansSum=0;
        for(int i=0;i<N;++i){
            while(!stack.isEmpty() && stack.peek()<=list[i]){
                stack.pop();
            }
            ansSum+=stack.size();
            stack.push(list[i]);
        }
        bw.write(ansSum+"\n");
        bw.flush();
        bw.close();
    }
}