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

[문제링크]

6198번: 옥상 정원 꾸미기

 

0. 관리인은 오른쪽의, 자기보다 낮은 건물만 볼 수 있다

 

1. 빌딩들이 스택에 들어있을 때, 새로운 빌딩이 들어왔다면 2가지 경우가 된다

• 이전 빌딩에서 관측 가능 : 이전 빌딩이 새 빌딩보다 높다
• 이전 빌딩에서 관측 불가 : 이전 빌딩이 새 빌딩보다 낮다

 

2. 관측 가능한 빌딩을 만날때까지, 관측 불가능한 빌딩들은 다 스택에서 버린다

• 스택에 [9,8,7,3,2,1] 이 있었다면, 5가 들어왔을때 3,2,1이 버려진다

 

3. 그 후 스택에 남아있는 빌딩들이 새 빌딩을 관측 가능한 빌딩들이다

• 3,2,1을 버린 후 [9,8,7] 이 빌딩들은 5를 관측 가능하다

 

4. 스택의 크기만큼 관측 카운트를 누적시킨 후 새 빌딩 높이를 스택에 넣는다

 

※ 건물의 갯수는 최대 8만이므로, 최대 가능한 관측 수는 1+2+.... +79999+80000이다

• 이는 (80000*80001)/2 = 대략 32억이므로, int 범위를 초과하니 long이나 uint 변수를 사용해야한다
• JAVA에는 uint가 마땅히 없으므로 long을 사용

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 = pint(br.readLine());
		long cnt=0;
		Stack<Integer> stack = new Stack<>();
		
		for (int i = 0; i < N; i++) {
			int h = pint(br.readLine());
			while(!stack.isEmpty() && stack.peek()<=h)stack.pop();
			cnt+=stack.size();
			stack.add(h);
		}
		System.out.println(cnt);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면