[BOJ] 백준 6198번 옥상 정원 꾸미기 (Java)

#6198 옥상 정원 꾸미기

난이도 : 골드 5 

유형 : 자료구조 / 스택 

6198번: 옥상 정원 꾸미기

▸ 문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

▸ 입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

▸ 출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

 

문제 풀이  

stack을 활용하는 자료구조 문제이다. 구하는 방법은 다음처럼 간단하다.

1. 이전에 위치한 빌딩 중 새로운 빌딩의 높이보다 낮은 빌딩은 모두 제거한다.
2. 새로운 빌딩을 추가한다.
3. stack에 남아있는 빌딩들은 새로운 빌딩보다 높으므로 해당 사이즈-1만큼 벤치마킹의 횟수를 카운트해준다.

 

 

풀이 코드 

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());
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		long result = 0;
		Stack<Integer> s = new Stack<>();
		for(int i=0; i<n; i++) {
			while(!s.isEmpty() && s.peek() <= arr[i]) {
				s.pop();
			}
			
			s.push(arr[i]);
			result += s.size()-1;
		}
		
		System.out.println(result);
	}
}