[白俊-java]6198号:屋上ガーデンを飾る

質問する

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

説明:

スタックを使うと簡単に解決できる問題です!

階にビルがある場合、新しいビルが入るのは2つの場合です.
(1)前に入ったビルで新しいビルが見える->前のビルの高さが入力したビルの高さより高い(stack.peek()>height)
(2)以前に入ったビルでは新しいビルが認識できない->以前のビルの高さが入力したビルの高さより低い(stack.peek()<=height)

で確認可能なビルに遭遇する前に、高さの低い建物または同じ建物が家屋から削除されます.
-> while (!stack.isEmpty() && stack.peek()<=height部

で確認できるビルに出会ったら、家の大きさを増やすことができます.
-> result += stack.size();

の新しいビルの高さをスタックに入れます.

注意事項
建物の個数の範囲は(1≦N≦80000)であるため、結果の範囲はintを超える可能性があるため、intではなくlongと宣言すべきである.

ソースコード

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));
		
		int N = Integer.parseInt(br.readLine());
		
		Stack<Integer> stack = new Stack<>();
		long result = 0;
		
		for (int i = 0; i < N; i++) {
			int height = Integer.parseInt(br.readLine());
			
			// 입력 받은 건물의 높이보다 작거나 같은 건물은 스택에서 삭제 -> 이전에 들어온 빌딩에서 새로운 빌딩을 확인할 수 없는 경우(높이가 더 높기 때문에 불가능)
			while (!stack.isEmpty() && stack.peek() <= height) {
				stack.pop();
			}
			
			result += stack.size();
			stack.push(height);
		}
		
		System.out.println(result);
	}

}

GITHUB

https://github.com/MinchaeGwon/BOJ/blob/master/BOJ%236198/src/Main.java