[백준, BOJ 6198] 옥상 정원 꾸미기 (java)

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

6198번: 옥상 정원 꾸미기

---

문제

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

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

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

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

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

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

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 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 ≤ $h_i$ ≤ 1,000,000,000)

출력

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

728x90

 

예제 입력 1

6
10
3
7
4
12
2

예제 출력 1

5

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// N 입력
		int N = Integer.parseInt(br.readLine());
		
		// 빌딩 높이 입력 
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		// 빌등의 오른쪽 건물들 중 가장 먼저 나오는 현재 빌딩보다 가장 높거나 같은 건물의 인덱스
		int[] rightIdx = new int[N];
		// 빌딩이 볼 수 있는 옥상 수를 담은 배열
		int[] numOfRoof = new int[N];
		
		// 오른쪽부터 시작
		rightIdx[N - 1] = N; //가장 오른쪽 건물은 볼 수 있는 건물이 없으니 건너뜀
		for (int i = N - 2; i >= 0; i--) {
			int tmpIdx = i + 1;
			while(tmpIdx < N && arr[i] > arr[tmpIdx]) { // rightIdx를 따라가며 건물 높이를 체크하다가 현재 건물보다 높은 건물이 나오면 스톱
				numOfRoof[i]++; // 한 칸 앞으로 이동했으니 + 1
				numOfRoof[i] += numOfRoof[tmpIdx]; // 다음 건물까지의 수  더해주기
				tmpIdx = rightIdx[tmpIdx]; // 다음 큰 건물로 이동
			}
			rightIdx[i] = tmpIdx;
		}
		
		// 모든 벤치마킹 가능한 빌딩 수의 합 구해주기
		long result = 0; // long 타입인 것에 주의..
		for (int i = 0; i < N; i++) {
			result += numOfRoof[i];
		}
		
		// 출력
		System.out.println(result);
	}

}