[백준 6198] 옥상 정원 꾸미기 (C++)

https://www.acmicpc.net/problem/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 ≤ hi ≤ 1,000,000,000)

 

출력

---

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

 

문제 풀이

---

스택을 이용한 문제.

1번 빌딩부터 N번째 빌딩까지 스택에 빌딩의 높이를 저장하며 해당 빌딩을 관찰할 수 있는 빌딩의 개수를 확인한다.

 

예시의 10 3 7 4 12 2의 경우,

첫번째 빌딩인 10의 경우 첫번째 빌딩이므로 이 빌딩을 관찰할 수 있는 빌딩이 없다.

스택에는 10을 넣어준다.

---

두번째 빌딩인 3의 경우 첫번째 빌딩에서 관찰이 가능하다. 스택의 top에 해당하는 10보다 작은 것이라고도 할 수 있다.

스택에 3을 넣어준다.

---

세번째 빌딩인 7의 경우 첫번째 빌딩에서 관찰이 가능하다. 스택에 top에 해당하는 3보다 크기 때문에, 두번째 빌딩에서는 관찰할 수 없으므로 pop한다. 다음 스택의 top에 해당하는 10보다 작기 때문에 관찰 가능하다. 마지막으로 스택에 7을 넣어준다.

---

네번째 빌딩인 4의 경우 스택의 top에 해당하는 7보다 작기 때문에 7의 높이를 가진 세번째 빌딩에서 관찰이 가능하다. 또한 각 빌딩마다 탐색할 때 스택의 top보다 작은 높이들은 모두 pop하기 때문에 스택에 저장되는 수는 내림차순이다. 따라서 스택의 이전에 저장된 값은 모두 7보다 큰 수이고, 4의 높이를 가진 네번째 빌딩을 볼 수 있기 때문에 스택에 저장된 수의 개수가 네번째 빌딩을 관찰할 수 있는 빌딩의 개수가 된다. 현재 스택의 size가 2이기 때문에 네 번째 빌딩은 2개 빌딩에서 관찰 가능하다.

 

같은 방식으로 모두 구해주면 된다.

아래는 코드.

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	stack<int> s;
	cin >> N;
	int* arr = new int[N];
	long long answer = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (int i =0; i < N; i++)
	{
		while (!s.empty())
		{
			if (arr[i] >= s.top())
			{
				s.pop();
			}
			else
			{
				break;
			}
		}
		answer += s.size();
		s.push(arr[i]);
	}
	cout << answer << "\n";
	return 0;
}