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

문제

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

설명

스택을 사용하면 쉽게 해결되는 문제였다!

1. 스택에 빌딩이 있는 경우 새로운 빌딩이 들어왔을 때 2가지의 경우로 나뉜다.
   (1) 이전에 들어온 빌딩에서 새로운 빌딩 확인 가능 -> 이전 빌딩의 높이가 입력 받은 빌딩의 높이보다 높음 (stack.peek() > height)
   (2) 이전에 들어온 빌딩에서 새로운 빌딩 확인 불가능 -> 이전 빌딩의 높이가 입력 받은 빌딩의 높이보다 낮음 (stack.peek() <= height)
2. 확인 가능한 빌딩을 만날 때까지 높이가 낮거나 같은 건물은 스택에서 삭제한다.
   -> while (!stack.isEmpty() && stack.peek() <= height) 부분
3. 확인 가능한 빌딩을 만나면 스택의 크기를 더해준다.
   -> result += stack.size();
4. 새로운 빌딩의 높이를 스택에 넣어준다.

주의할 점
건물의 개수의 범위가 (1 ≤ N ≤ 80,000)이므로 result의 범위가 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