[백준] 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이다.

 

시간 제한 : 1초

메모리 제한 : 128MB

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

 

---

입력

빌딩의 개수 (1 ≤ N ≤ 80,000)

빌딩의 높이 hi (1 ≤ hi ≤ 1,000,000,000)

 

출력

각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합

---

 

문제 접근 방식 

 

빌딩이 이런식으로 서 있으며, 특정 빌딩은 자신의 오른쪽에 위치하면서 자신보다 높이가 낮은 빌딩의 옥상을 볼 수 있다. 

이러한 접근에서 도출할 수 있는 풀이 방법은 아래와 같다. 

첫번째 빌딩부터 N-1번째 빌딩까지 돌면서 자신보다 낮은 빌딩이 몇 개 인지 찾는 방법.

이 방법은 해당 문제에서는 사용할 수 없다.

왜냐면 N 이 최대 80,000이기 때문에, 최악의 경우 O(N^) 의 시간복잡도를 보인다. 실제로 계산해보면 
( N * (N-1) )/2 로, 시간 제한인 1초를 훌쩍 넘긴다. 

 

그럼 다르게 접근해보자. 

2중 for문을 쓸 수 없다는 것은, 0부터 N-1까지를 순회하는 for문 1개로 정답을 도출하는 방법을 찾아야 한다는 것이다. 
기존에는 선정한 빌딩이 주체로써, 자신보다 높이가 낮은 빌딩 개수를 세고 있다. 

높이 10인 빌딩은 높이 3, 7, 4 인 빌딩의 옥상을 볼 수 있고, 

높이가 3인 빌딩은 높이가 7인 빌딩에 의해 다른 빌딩의 옥상을 하나도 볼 수 없다.

높이가 7인 빌딩은 높이가 4인 빌딩의 옥상을 볼 수 있고, 높이가 12인 빌딩의 옥상은 볼 수 없다. ... 

 

이 문제는 이렇게도 해석할 수 있다.

어떤 빌딩 A가 다른 빌딩에 의해 관측 가능한 개수 이다.

예를 들어, 예제에서 높이가 4인 빌딩은 자신의 왼쪽에 있는 빌딩 중 높이가 10인 빌딩, 높이가 7인 빌딩에 의해 옥상이 관측될 수 있다. 

 

 

이러한 흐름에 따라, 0부터 N-1까지 for문을 돌며, i 번째 빌딩을 관측할 수 있는 개수를 누적해나가면 되는 것이다.

A 라는 빌딩이 i 번째 빌딩의 왼쪽에 위치하면서, 그 높이가 i 번째 빌딩의 높이보다 높다면, 빌딩A는 i 번째 빌딩을 관측할 수 있는 빌딩이다. 반면에, 빌딩A가 i번째 빌딩의 높이보다 낮다면, 빌딩A는 i번째 빌딩을 관측할 수 없다. 

높이3 짜리 빌딩은 i가 3 이상일 때 무조건 2번 빌딩에게 가려서 i번째 빌딩을 관측할 수 없다.

4,7,10칸짜리 빌딩은 12칸 짜리 빌딩을 관측할 수 없다.

 

이러한 방식으로 동작하게 된다면, i번째 빌딩은 i-1 부터 0까지 탐색을 하며, i번째 빌딩보다 높은 빌딩을 찾을 때까지 자신보다 낮은 빌딩을 전부 배제하면 된다. (높은 빌딩 왼쪽에 있는 낮은 빌딩은 어차피 높은 빌딩에 의해 i번째 빌딩을 보지 못하기 때문이다.) 

 

코드

import java.util.*;
import java.io.*;

public class Main
{
	static int N;
	static long buildings[];
	static long result =0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		buildings = new long[N];
		for(int i=0; i<N; i++) {
			buildings[i] = Long.parseLong(br.readLine());
		}

		ArrayDeque<Long> q = new ArrayDeque<Long>();

		for(int i=0; i<N; i++) {

			while(!q.isEmpty()) {

				long building = q.pollLast(); //i번째 빌딩의 왼쪽에서부터 탐색을 시작한다.
			    //q에서 poll 함으로써, i번째 빌딩보다 낮은 빌딩은 누적 대상에서 제외
				if(buildings[i] < building) { //왼쪽에서 자신보다 큰 빌딩을 만났다면 
					q.offerLast(building); //i번째 빌딩의 옥상을 볼 수 있으므로 다시 queue에 넣음
					break;
				}
			}
			result+= q.size(); //해당 queue에는 i번째 빌딩을 관측할 수 있는 빌딩들이 저장됨
			
			q.offerLast(buildings[i]); // 다음 처리를 위해 i번째 빌딩을 queue에 넣음 
		}
	
	System.out.println(result);
	}

}