[BOJ] 6198. 옥상 정원 꾸미기 (🥇, 스택)

🔗

풀이

이 문제의 핵심은 결국 해당 빌딩의 위치보다 더 높은 높이를 가지는 빌딩이 오른쪽에서 몇번째 위치에 존재하느냐이다. 완전 탐색 방식으로 오른쪽에 있는 빌딩의 개수를 셀 수도 있겠지만 전체 빌딩의 개수가 8만개이기 때문에 시간 복잡도가 O(n^2) 면 계산이 불가능하다.

결국 오른쪽에 위치한 더 높은 빌딩의 높이와 현재 빌딩 사이의 거리가 중요하다. 더 오른쪽에 위치한 높은 빌딩의 인덱스와 현재 빌딩 인덱스 값만 알면 된다. 왼쪽부터 값을 차례대로 저장하다가 더 높은 빌딩의 값을 만나게 되면 거리를 계산하면 된다. 차례대로 값을 저장하고 값을 꺼낼때는 거꾸로 꺼내는 것은 FILO 구조를 가지는 스택이 적절하다.

스택이 비어있다면 무조건 값을 추가한다. 하지만 스택이 비어 있지 않고 스택의 가장 상위에 있는 값이 현재 비교하려는 빌딩 높이보다 작다면 해당 빌딩 인덱스와 현재 비교하려는 빌딩 인덱스 사이의 거리를 계산한다. 이 값은 해당 빌딩이 볼 수 있는 빌딩의 개수이다. 이제 스택의 상위에 있는 해당 빌딩 인덱스의 값을 제거하고 현재 빌딩 인덱스 값을 스택에 추가한다. 이런 식으로 현재 빌딩 높이보다 왼쪽에 있는 더 작은 빌딩 높이들은 다 제거하면서 계산하면 된다. 만약 현재 빌딩 높이보다 더 높은 빌딩이라면 아직 자신보다 오른쪽에 있으면서 더 높은 빌딩을 찾지 못한것이므로 그냥 값을 비교하거나 제거하지 않고 현재 빌딩 높이를 바로 추가하면 된다.

package Baekjoon.Gold;

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

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

        int N = Integer.parseInt(br.readLine());
        long[] buildings = new long[N+1];
        for (int i = 0; i < N; i++) {
            buildings[i] = Long.parseLong(br.readLine());
        }
        buildings[N] = Long.MAX_VALUE;

        Stack<Integer> st = new Stack<>();
        long[] count = new long[N];
        for (int i = 0; i < N + 1; i++) {
            while (!st.isEmpty() && buildings[st.peek()] <= buildings[i]) {
                /**
                 * 스택의 가장 위에 있는 값보다 현재 비교하려는 빌딩 높이가 더 높다면 제거 해야 함
                 */
                count[st.peek()] = i - st.peek() - 1L;
                st.pop();
            }
            st.add(i);
        }

        System.out.println(Arrays.stream(count).sum());
    }
}