백준 - 2493번 : 탑 (C++)

풀이 방법 : 스택

처음에는 단순무식하게 풀었다. 가장 가까운 녀석부터 검사해가면서 왼쪽의 탑의 전파가 닿은 탑들을 대상으로 검사해주는 방식으로 검사했다.

#include <iostream>
#include <vector>

using namespace std;

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

	int N;

	cin >> N;

	vector<int> vecTower(N);
	vector<int> vecAnswer(N);

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

	vecAnswer[0] = 0;

	for (int i = 1; i < N; ++i)
	{
		if (vecTower[i] <= vecTower[i - 1])
			vecAnswer[i] = i;

		else
		{
			int Idx = vecAnswer[i - 1] - 1;

			while (Idx != -1)
			{
				if (vecTower[i] <= vecTower[Idx])
					break;

				Idx = vecAnswer[Idx] - 1;
			}

			if (Idx == -1)
			{
				vecAnswer[i] = 0;
				continue;
			}

			if (vecTower[i] <= vecTower[Idx])
				vecAnswer[i] = Idx + 1;

			else
				vecAnswer[i] = vecAnswer[Idx];
			
		}

	}
	
	for (int i = 0; i < N; ++i)
	{
		cout << vecAnswer[i] << ' ';
	}
}

이렇게 해도 풀리긴 했으나 어차피 루프를 돌릴것이고 더 가까운 녀석들 부터 검사를 할거라면
stack을 사용하는 것이 더 깔끔할 것 같아서 다시 풀었다.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

	int N;
	cin >> N;

	vector<int> vecTower(N);
	vector<int> vecAnswer(N);

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

	stack<int> sIdx;
	sIdx.push(0);

	for (int i = 1; i < N; ++i)
	{
		while (!sIdx.empty())
		{
			int Idx = sIdx.top();

			if (vecTower[i] <= vecTower[Idx])
			{
				vecAnswer[i] = Idx + 1;
				break;
			}

			else
				sIdx.pop();
		}

		sIdx.push(i);
	}
	

	for (int i = 0; i < N; ++i)
	{
		cout << vecAnswer[i] << ' ';
	}
}