[백준] 6198: 옥상 정원 꾸미기 - JAVA

in Algorithm on 자료 구조

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

풀이

그리디스러운 문제였다. 알고리즘 분류는 자료 구조, 스택.

자기보다 오른쪽에 있는 빌딩을 보는데 높이가 자기보다 낮은 빌딩을 볼 수 있다.

중간에 같거나 높은 빌딩을 만나면 그 다음부터 빌딩은 보지 못한다.

나는 현재 빌딩의 높이를 기준으로 이 빌딩을 볼 수 있는 왼쪽 빌딩들의 개수를 카운트했다.

stack에 빌딩의 높이를 담으면서 진행하며 현재 빌딩보다 낮은 빌딩을 스택에서 빼줬다.

stack의 사이즈를 답에 더해주고 현재 빌딩을 stack에 넣어주면 끝.

메모리: 24236KB

시간: 324ms

언어: Java 11

코드

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));
        int N = Integer.parseInt(br.readLine());

        Stack<Long> bldg = new Stack<>();
        long ans = 0;
        for(int i = 0; i < N; i++) {
            long h = Long.parseLong(br.readLine());
            while(!bldg.isEmpty() && bldg.peek() <= h) {
                bldg.pop();
            }
            ans += bldg.size();
            bldg.add(h);
        }

        System.out.println(ans);
    }

}