[백준/java] 6198. 옥상 정원 꾸미기

sbin·2025년 2월 16일

백준 스택

코테공부

목록 보기

12/15

문제 보기

문제

입력 : 빌딩의 갯수 N (1 <= N <= 8*10^4),
각 빌딩의 높이 h (1 <= h <= 10^9)

출력 : 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합

확인할 수 있는 옥상의 조건은

자신(빌딩)보다 빌딩번호가 크다.
2. 자신보다 높이가 작다.

두 조건을 모두 만족해야 한다.

문제 풀이

직관적으로 떠오른 생각은 이중반복문을 이용한 일일히 빌딩 크기를 비교하는것이지만, O(N^2)으로 시간초과가 난다.

빌딩번호가 큰 경우만 비교하면 되니, i번 빌딩의 높이 h가 입력될 때마다, h를 확인할 수 있는(h보다 높은) 빌딩만 스택에 남기고, 해당 빌딩(i번 h 높이)을 확인가능한 빌딩의 갯수를 총 횟수 cnt에 매번 더한다.
예시를 이용하면 다음과 같다.

스택 그림을 보면, 스택은 항상 내림차순을 유지하는 단조 감소 스택이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long cnt = 0;
        int N = Integer.parseInt(br.readLine());
        Stack<Long> stack = new Stack<>();

        for(int i = 0; i < N; i++){
            long h = Long.parseLong(br.readLine());

            while (!stack.isEmpty() && h >= stack.peek()){
                stack.pop();
            }
            stack.push(h);
            cnt += stack.size() - 1;
        }
        System.out.println(cnt);
    }
}