[BaekJoon] 6198번 - 옥상 정원 꾸미기 [Java][C++]

문제 링크

---

1. 아이디어

각 빌딩에서 오른쪽에 위치한 빌딩만 볼 수 있을 때 자신보다 높이가 낮은 빌딩의 개수를 각각 찾는 문제다. 빌딩의 수가 최대 80,000개여서 O(N²)의 시간 복잡도로는 해결할 수 없는데 스택 자료구조를 활용하면 해결할 수 있다.

스택은 왼쪽에서 오른쪽 순서로 빌딩을 담는다. 현재 빌딩에 대해 왼쪽에 위치한 빌딩들은 모두 스택을 거친 적이 있는 빌딩들이 된다. 현재 빌딩의 높이를 h라 할 때, 스택의 top에 위치한 빌딩의 높이가 h 보다 낮거나 같다면 top에 위치한 빌딩은 현재 빌딩의 옥상을 보지 못한다. 한번 가려지면 앞으로도 쭉 어떤 빌딩의 옥상도 못 보므로 이 빌딩은 더 이상 필요 없는 정보가 되며 스택에서 제거한다. top 이전에 스택에 저장한 빌딩 역시 마찬가지로 h 보다 낮거나 같으면 제거하면 되며 스택에 빌딩이 존재하는 동안 낮거나 같은 높이를 가진 빌딩은 전부 제거하면 된다. 이러면 스택에는 현재 빌딩보다 높이가 높은 빌딩들이 남게 되며 이 빌딩들이 현재 빌딩의 옥상을 볼 수 있으므로 스택의 크기가 현재 빌딩을 볼 수 있는 빌딩의 수가 된다. 현재 빌딩에 대해 볼 수 있는 빌딩의 수를 셌다면 이제 현재 빌딩을 스택에 담아주면 된다. 모든 빌딩을 순서대로 한번은 스택에 담고 담을 때는 항상 top 보다 작을 때만 담으므로 이 스택은 단조 스택이 된다.

---

2. 코드

1. 풀이 [Java]

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

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

        Deque<Integer> stack = new ArrayDeque<>();
        long cnt = 0;

        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            int h = Integer.parseInt(br.readLine());

            while (!stack.isEmpty() && stack.peek() <= h) {
                stack.pop();
            }

            cnt += stack.size();
            stack.push(h);
        }

        System.out.println(cnt);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    stack<int> st;
    long long cnt = 0;

    int n;
    cin >> n;

    while (n--) {
        int h;
        cin >> h;

        while (!st.empty() && st.top() <= h) {
            st.pop();
        }

        cnt += st.size();
        st.push(h);
    }

    cout << cnt;
}

---

3. 디버깅

오른쪽에 위치한 같은 높이의 빌딩도 하나는 볼 수 있는 줄 알았다. 설명이 약간 부실한거 같다.

---

4. 참고

없음.

---