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

1. 문제

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

 

2. 풀이과정

1. 먼저 스택이 비어있는 상태니까 첫번째 빌딩의 높이를 스택에 넣는다.
2. 두번째 입력부터 아래 로직을 거친다.

• 스택에 들어있는 빌딩 높이들 중에 입력받은 빌딩의 높이보다 낮은 빌딩은 다 뺍니다.
• 낮은 빌딩을 다 뺐다면 스택에는 입렵받은 빌딩보다 높거나 아니면 모두 다 빠져서 비어있을 겁니다.
• 이때 스택의 남은 빌딩 수가 곧 입력받은 빌딩을 볼 수 있는 빌딩이므로 count에 저장합니다.

3. 위 3단계가 끝나면 스택에 입력받은 빌딩을 스택에 넣어줍니다

 

예시

1. 첫번째 입력

건물5개이고 높이 {10, 5, 1 ,3 ,14}가 순차적으로 입력됩니다.

현재 스택이 비어있으니 현재 입력 push 합니다.
Stack
[ 10 ]

 

2. 두번째 입력

5보다 낮은 빌딩은 스택에 없다. 스택에 남아있는 빌딩 수가 곧 5를 볼 수 있는 빌딩수(count에 1 더한다.)
나를 볼 수 있는 빌딩수 처리가 끝났으니 push한다.
Stack
[ 10 5 ]

 

3. 세번째 입력

1보다 낮은 빌딩은 스택에 없다. 스택에 남아있는 빌딩 수가 곧 1를 볼 수 있는 빌딩수 (count에 2 더한다.)
나를 볼 수 있는 빌딩수 처리가 끝났으니 push한다.
Stack
[ 10 5 1 ]

4. 네번째 입력

3보다 낮은 빌딩은 스택에 있다. 3보다 낮은 빌딩을 다 pop 시킨다.
Stack
[ 10 5 ] <- 1이 pop, 더 이상 3보다 낮은 빌딩은 없다. 스택에 남아있는 빌딩수가 곧 3을 볼 수 있는 빌딩수 (count 2에 2 더한다.)
나를 볼 수 있는 빌딩수 처리가 끝났으니 push한다.
Stack
[ 10 5 3 ]

5. 다섯번째 입력

14보다 낮은 빌딩이 스택에 있다. 14보다 낮은 빌딩을 다 pop 시킨다.
Stack
[ ] <- 3, 5, 10 전부 pop 되어버림. 스택에 남아있는 빌딩수가 없으니 14를 아무도 보지 못한다.
스택이 비었어버렸으니 push한다.
Stack
[ 14 ]나면 스택에 입력받은 빌딩을 스택에 넣어줍니다.

 

주의할 점

 빌딩의 개수 N개가 (1 <= N <= 80,000)이므로 빌딩의 높이가 80000부터 1까지 나열되어 있다면

볼 수 있는 건물 갯수는 1부터 n까지의 합으로 나타낼 수 있다. 이는 n(n+1)/2이다.

80,000의 제곱은 6,400,000,000이므로 int형으로 나타낼 수 없다.

따라서 count는 long long int형으로 선언해줘야한다.

 

3. C++ 정답코드

#include <iostream>
#include <vector>

using namespace std;

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

	int n;
	cin >> n; //빌딩 개수 입력

	vector <int> v(n);  //빌딩 높이를 받을 벡터 선언
	vector <int> s;     //빌딩 높이들을 적절하게 넣을 스택 선언
	for (auto& i : v)
		cin >> i;   //각 빌딩 높이 입력

	long long int count = 0;  //count가 int형을 넘어서기에 long long int type으로 둠
	for (const auto& height : v) // 모든 빌딩 높이를 하나씩 순회한다.
	{
		while (true)
		{
			if (s.empty()) //스택이 비었다면 현재 빌딩 높이 스택에 push
			{
				s.push_back(height);
				break;
			}
			if (height < s.back()) //현재 빌딩 높이가 스택의 top보다 높은 빌딩이라면(볼 수 있는 빌딩이라면)
			{
				count += s.size();
				//스택에는 현재 빌딩보다 높은 빌딩 밖에 없으니 스택의 크기 = 현재 빌딩을 볼 수 있는 빌딩 수
				s.push_back(height);
				break;
			}
			s.pop_back(); //현재 빌딩이 스택의 top보다 높다면(어짜피 나를 볼 수 없는 빌딩이니) 전부 pop
			//스택이 비거나 현재 빌딩보다 높은 top이 나올때까지 pop한다.
			// 언제까지 pop 할까?
			//case 1. 스택이 비면 나를 볼 수 있는 빌딩은 없다는 뜻이니 스택에 push
			//case 2. 나보다 높은 빌딩이 나온다면 그때 스택의 크기 = 나를 볼 수 있는 빌딩 수 를 count에 추가
		}
	}
	cout << count;
	return 0;
}

 

4. 새로 알게된 점

monotone stack : 스택의 원소를 중복을 허용하지 않고 오름차순, 또는 내림차순으로 유지시키면서 값을 저장시키는 것

새 항목이 push 될때 단조를 유지하면서 저장함. push 전에 단조를 유지할 수 있도록 pop을 수행한다.

이때 정렬하는 과정에서 발생하는 정보가 유용하게 쓰인다.

이 문제에서 스택이 모노톤 스택의 형태로 유지된다!