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

 

이 문제를 보자마자 떠오로는 생각은 각 관리자가 보고있는 건물보다 낮은 건물들을 모조리 세는 방법이다.

하지만 이 방법을 사용하게 되면 ,

시간 초과가 발생하고 만다.

왜냐하면 무조건 끝까지? 가야 하기 때문이다.

즉, 100개가 있다면 낮은 건물을 세는데, n+i번 더 해야하는 이야기다.

 예를들어, 건물 크기가 10 3 7 4 12 2 이라고 하자

그러면 10부터 2까지의 정보를 전부 배열에 집어 넣고,

10보다 작은 건물들을 센다.(이때, 10보다 큰 건물이 발생하면 세지 않는다.)

10 3 7 4 까지 세고

그 다음은 3, 그 다음은 7 이런식으로 건물을 세고 다시 돌아오고를 반복해야한다.

다른 방법을 갈구해야 한다.

곰곰히 생각해 본결 결과,

자신보다 큰 건물이 등장하면 그 안에 있는 건물들과 크기를 비교 해서 작은 건물들은 모조리 지우면 된다.

10    10밖에 저장이 불가하기 때문에 10만 저장한다.

10 3  3은 10보다 작으므로 10입장에서는 건물 크기 3은 관찰이 가능하다.

10 x 7  7은 10보다 작으므로 10은 관찰이 가능하지만, 3은 관찰이 불가하므로 삭제한다.

10 7 4   4는 10,7모두 에서 관찰이 가능하다.

x x  x 12  12를 관찰할 수 있는 건물은 존재하지 않는다.

12 2   2는 12보다 작으므로 건물 크기 2를 관찰할 수 있다.

 

그러면 자기자신은 관찰이 불가하므로 그것들을 정렬해보면

0 1 1 2 0 1 이 나온다. 다 더하면 5라는 숫자가 나와 정답이다.

어떻게 보면 이것도 반복문이 2개 나오기 때문에 O(n^2)이라고 생각할 수 있을 것 같다.

하지만 처음에 말한 방법은 다시 처음부터 돌아가야한다는 단점이 있지만

두 번째 방법은 그럴 필요가 없다.

왜냐하면 스택에 있는 내용들만 비교하면 되기 때문이다.

스택이 작아지면 질수록 그 만큼 시간 복잡도도 작아지기 때문에 어떻게 보면 더 효율적인 방법일 것 같다.

 

#include <bits/stdc++.h>
using namespace std;
long long arr[80000];
int main(void) {    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  int n;
  cin >> n;

  for(int i = 0; i<n;i++) {
    cin >> arr[i];
  }
  long long cnt = 0;
  stack<long long> s;  
   for(int i = 0; i<n;i++) {
    while(!s.empty() && s.top() <= arr[i]) {
        s.pop();
    }
    s.push(arr[i]);   
    cnt += s.size();
  }

  cout << cnt - n << "\n";

}
 

 * 비어있을때 pop하면 오류생기니까....

 

typedef long long ll;
typedef stack<int> si;
#define sf1(a) cin >> a
#define rep(i,a,b) for(int i = a; i < b; i++)
#define sz(a) ((int)(a.size()))

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	sf1(N);
	si S;
	ll tot = 0;
	rep(i, 0, N) {
		int H;
		sf1(H);
		while (!S.empty() && S.top() <= H) S.pop();
		tot += sz(S);
		S.push(H);
	}
	pf1(tot);
}