[Baekjoon] 6198번: 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

문제 설명

빌딩 관리인들은 다른 빌딩의 옥상을 벤치마크하고 싶어 한다. 그래서 자기 빌딩보다 낮은 빌딩들의 옥상 정원을 보며 본인 소유의 빌딩 옥상 정원에 대한 고민을 한다. 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. 그리고 본인 소유 빌딩과 높이가 같거나 큰 경우엔 옥상을 볼 수 없다.

 

예) 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이다. 이를 출력하면 된다.

 

입력 조건은 다음과 같다.

• 첫 번째 줄에 빌딩의 개수 N이 입력된단.(1 \(\leq\) N \(\leq\) 80,000)
• 두 번째 줄부터 N+1번째 줄까지 각 빌딩의 높이가 \(h_i\) 입력된다.(1 \(\leq\) \(h_i\) \(\leq\) 1,000,000,000)

풀이 방법

스택을 활용하면 효율적으로 해결할 수 있다. 주의할 점은 N이 80,000까지 주어질 수 있는데 만약 80,000부터 1까지 모두 더하면 약 32억 정도가 된다. 따라서 결과값을 저장할 count를 int가 아닌 long으로 지정해야 한다. 나머지는 주석으로 설명해 놓았으니 코드를 바로 따라가자.

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

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

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

        // 범위 초과 예방을 위한 long
        long count = 0;
        
        for (int i = 0; i < N; i++) {
            int building = Integer.parseInt(br.readLine());

            // 스택이 비어있지 않고
            // 맨 오른쪽 빌딩 높이가 현재 입력받은 빌딩 높이보다 작거나 같으면
            // 현재 맨 오른쪽 빌딩은 현재 빌딩 옥상을 볼 수 없으므로
            // 스택에서 pop한다.
            while (!buildings.isEmpty() && buildings.peek() <= building) {
                buildings.pop();
            }

            // 다른 빌딩들을 볼 수 있는 빌딩들의 수를 카운팅한다.
            count += buildings.size();
            // 스택에 현재 빌딩 높이를 push한다.
            buildings.push(building);
        }

        System.out.print(count);
    }
}