[백준] 6198 옥상 정원 꾸미기 자바(Java)

풀이

• 기존에 지나온 빌딩 중 새로운 빌당보다 낮은 빌딩만 저장
• 마지막 서있는 곳보다 새로운 빌딩의 높이가 낮으면 같이 지나갈 수  있기 때문
• 스택에 가장 마지막 빌딩 높이(마지막 서있는 곳) <= 새로운 높이
  • 새로운 높이보다 큰 거만 남기고 제거

윷놀이처럼 업혀서 간다고 생각하면 이해하기 쉽다.

 

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long result = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            int tmp = Integer.parseInt(br.readLine());
            // 이전에 있는 빌딩 중 새로운 빌딩의 높이보다 낮으면 모두 제거
            while (!stack.isEmpty() && stack.peek() <= tmp) {
                stack.pop();
            }
            // 빈 stack or 새로운 빌딩보다 큰 빌딩만 남음.
            // 즉, 새로운 빌딩을 볼 수 있는 빌딩들만 남음
            stack.push(tmp);
            result += stack.size() - 1;
        }
        System.out.println(result);
    }
}