[BaekJoon] 6198 옥상 정원 꾸미기

1.  문제 링크

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

2.  문제

요약

• N개의 빌딩이 있고 빌딩 관리인들은 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어합니다.
• i번째 빌딩의 키가 $h_i$이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있습니다.
• 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 빌딩의 옥상은 보지 못합니다.
• 각 관리인들이 벤치마킹이 가능한 빌딩의 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 80,000보다 작거나 같은 빌딩의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에는 1보다 크거나 같고 1,000,000,000보다 작거나 같은 각 빌딩의 높이 $h_i$가 주어집니다.
• 출력: 첫 번째 줄에 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력합니다.

3.  소스코드

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

public class Main {
	public long getSumOfBuliding(int[] heights) {
		long result = 0;
		Stack<Integer> stack = new Stack<Integer>();
		for(int i = 0; i < heights.length; i++) {
			while(!stack.isEmpty() && stack.peek() <= heights[i]) {
				stack.pop();
			}
			stack.push(heights[i]);
			result += stack.size() - 1;
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] heights = new int[n];
		for(int i = 0; i < n; i++) {
			heights[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getSumOfBuliding(heights) + "\n");
		bw.flush();
		bw.close();
	}
}