[백준/boj.kr] 6198번 옥상 정원 꾸미기(JAVA)

옥상 정원 꾸미기 문제 보기

 

1. 문제 정의

높이가 h(1), h(2), h(3) ... h(N)인 빌딩 N개가 있을 때, 각 빌딩에서 다른 빌딩의 옥상을 관찰 가능한 갯수를 구해야 하는 문제입니다.

 

문제에서의 빌딩들을 예시로 들자면, 위와 같이 6개의 빌딩이 있고 각각 높이가 주어져 있습니다. 각 빌딩에서 오른쪽을 바라 볼 때 옥상이 관찰 가능한 빌딩을 카운팅 해보면 됩니다. 1번째 빌딩에서는 2, 3, 4 빌딩을 볼 수 있고, 2번 빌딩에서는 볼 수 있는 빌딩이 없으며, 3번 빌딩에서는 4번 빌딩을 볼 수 있습니다.

 

 

2. 풀이 방법 탐색

이 문제의 핵심은 i번째 빌딩의 높이 h(i)를 기준으로 이전 빌딩들 중, i번째 빌딩의 높이 h(i)보다 낮은 빌딩은 체크할 필요가 없다는 점 입니다. 위의 예시에서 1, 2, 3, 4번째 빌딩들을 순으로 관찰 가능한지를 체크해 오다가, 5번째 빌딩에서 가로막혀 버리기 때문에 1, 2, 3, 4에서의 확인했던 내용들을 확인할 필요가 없어지게 됩니다. 5번째 빌딩부터 다시 관찰 가능한 다음 빌딩이 무엇일까를 확인해 보면 되는거죠. 이러한 방식은 '모노스택' 이론에 해당하는 문제 입니다. 기본적인 스택 기능을 가지며 모든 원소들이 오름차순(혹은 내림차순)을 유지하도록 하며 체크하는 방식 입니다.

 

1번째 빌딩의 높이는 10입니다. 이 높이 10을 스택에 우선 담아 줍니다.

2번째 빌딩의 높이는 3인데, 높이 10인 1번째 빌딩에서 관찰이 가능하기에 충분한 높이 입니다. 2번째 빌딩의 높이 3도 스택에 담아 줍니다.

3번째 빌딩의 높이는 7 입니다. 이 때 높이 3인 2번째 빌딩에서는 3번째 빌딩의 옥상을 볼 수 없습니다. 2번째 빌딩의 높이가 3번째 빌딩의 높이보다 낮기 때문입니다. 그래서 스택에 들어있던 높이 3을 pop해주고 높이 7을 push해 줍니다.

4번째 빌딩의 높이는 4 입니다. 이 4라는 높이는 1번째, 3번째 모두에서 관찰하기에 충분한 높이 입니다. 그래서 높이 4를 stack에 push해 줍니다. 이 때 스택에 저장되어 있는 값이 높이 순으로 정렬되어 있음을 눈치채신 분도 계실 겁니다.

5번째 빌딩의 높이는 12 입니다. 이 높이는 이전에 체크해왔던 다른 빌딩들에 비해 높이가 가장 높습니다. 그래서 stack에 저장되어 있는 1, 3, 4빌딩의 높이 값들을 전부 pop하고 12를 새로 push해 주면 됩니다.

이러한 순으로 어떤 빌딩들을 관찰이 가능할지 stack에 값을 저장해주게 되고, 그 때 stack에 저장되어 있던 순간의 합이 각 빌딩에서 관찰 가능한 빌딩들의 개수가 됩니다. 위 예시에서 1번째 빌딩의 높이 10이 stack에 들어있던 타이밍을 확인해 봅시다. 2, 3, 4 빌딩을 확인하면서 높이 10은 stack에 3번 저장되어 있었습니다(2번째일 때 1번, 3번째일 때 1번, 4번째일 때 1번). 즉, 1번째 빌딩에서 관찰 가능한 빌딩의 개수는 3개가 됩니다. 같은 방식으로 2번째 빌딩의 높이 3이라는 값은 다른 빌딩들을 바라 볼 때 stack에 저장되어 있던 적이 없었기에 관찰 가능한 빌딩의 개수는 0입니다. 3번째 빌딩의 높이 7은 4번째 빌딩의 높이 4를 바라봤을 때 1번 stack에 저장되어 있었기에 관찰 가능한 빌딩의 개수는 1이 됩니다.

 

 

 

3. 문제 풀이

(1)조건 체크

문제에서 주어지는 빌딩의 개수는 80,000개 이하이고 높이는 1,000,000,000(10억)이하 입니다. 예를 들어 1번째 빌딩의 높이가 10억, 2번째 빌딩의 높이가 999,999,999이고 3번째 빌딩의 높이가 999,999,998이고 4번째 빌딩의 높이가 999,999,997... 순으로 주어지게 된다고 가정해 봅시다. 그러면 1번째 빌딩은 자기 자신을 제외한 79,999개 관찰이 가능하고, 2번째 빌딩도 자기 자신을 제외하고 79,998개 관찰이 가능하며 3번째 빌딩은 79,997개 관찰이 가능해 집니다. 정답을 내기 위해 벤치마킹이 가능한 빌딩의 수를 합쳐 보면, 80,000+79,999+79,998+...+1이 됩니다. 이를 등차급수 공식으로 계산해 보면 다음과 같습니다.

 

$$ \sum_{1}^{80,000}x = \frac{80,000*80,001}{2}=3,200,040,000 $$

 

이 값은 약 32억으로 int 범위를 넘어가기 때문에 정답을 출력할 변수는 long을 선언해 줘야 합니다.

 

 

(2) 최종 소스

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

public class Boj6198 {

	public static Stack<Integer> stack = new Stack<>();
	public static long ans; // long으로 선언!
	
	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());
		
		for(int i=0; i<N; i++) {
			
			int height = Integer.parseInt(br.readLine());
			
			while(!stack.isEmpty()) {
				
				if(stack.peek() <= height) {
					// i번째 빌딩보다 낮거나 같은 애들은 빼버린다.
					stack.pop();
				}
				else break;
			}
			ans += stack.size(); //스택 사이즈를 더함으로써, 벤치마킹 가능한 개수를 더해준다.
			stack.push(height); //i번째 빌딩의 높이를 넣어준다.
		}
		bw.write(String.valueOf(ans));
		bw.close();
	}
}

 

(3) 결과