백준 - 6198번 : 옥상 정원 꾸미기(C++)

풀이 방법 : 스택

오른쪽에 있는 건물만 볼 수 있으므로 오른쪽 끝에서부터 건물 번호를 스택에 넣어두고 시작하자

반복문을 오른쪽에서부터 돌려가면서 검사할 때 만약 스택에서 숫자를 꺼냈을 때 현재의 건물보다 낮은 높이의 건물일 경우 스택에서 pop해준다.

높거나 같은 높이의 건물일 경우 스택에서 꺼낸 건물과 현재 건물 사이에 위치한 건물들을 볼 수 있다는 의미이다. 번호를 이용해서 그 숫자를 구해줘서 정답에 더해주자.

만약 스택이 빌 때까지 자기보다 높거나 같은 높이의 건물을 발견하지 못했을 경우 자신의 오른쪽에 있는 건물들은 모두 볼 수 있다는 의미이므로 자신의 오른쪽에 있는 건물의 수를 정답에 더해주자.

루프가 끝났을 때 현재의 건물의 번호를 스택에 넣어주는 것도 잊지 말아야한다.

그리고 입력으로 주어지는 N이 80000이므로 최대로 나올 수 있는 정답의 수는 79999 + 79998 ...... + 1 일 것이다. 이를 계산해보면 알겠지만 int로 표현할 수 있는 최댓값을 넘기에 그보다 더 큰 정수를 표현할 수 있는 자료형으로 답을 구해야한다.

#include <iostream>
#include <stack>

using namespace std;

int Height[80001] = {};

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

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> Height[i];
	}

	stack<int> sIdx;
	sIdx.push(N - 1);

	unsigned int Answer = 0;

	for (int i = N - 2; i >= 0; --i)
	{
		while (!sIdx.empty())
		{
			int NextIdx = sIdx.top();

			if (Height[i] <= Height[NextIdx])
			{
				Answer += NextIdx - i - 1;
				break;
			}

			else
			{
				sIdx.pop();
			}
		}

		if (sIdx.empty())
		{
			Answer += (N - 1) - i;
		}

		sIdx.push(i);
	}

	cout << Answer;
}