[백준 C++] 1874 스택 수열 - 자료구조

1874번: 스택 수열

 

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

int main()
{
	bool possible = true;

	int n = 0;
	cin >> n;

	vector<int> sequence;
	sequence.reserve(n);
	for (int i = 0; i < n; ++i)
	{
		int inputNumber = 0;
		cin >> inputNumber;
		sequence.emplace_back(inputNumber);
	}

	stack<int> outputStack;
	for (int i = n; i > 0; --i)
	{
		outputStack.push(i);
	}

	queue<bool> result;
	stack<int> inputStack;
	for (int i = 0; i < n; ++i)
	{
		while ((inputStack.empty() || inputStack.top() < sequence[i])
			&& !outputStack.empty())
		{
			inputStack.push(outputStack.top());
			outputStack.pop();
			result.push(true);
		}

		if (inputStack.top() == sequence[i])
		{
			inputStack.pop();
			result.push(false);
			continue;
		}
		else
		{
			possible = false;
			break;
		}
	}

	if (!possible)
	{
		cout << "NO\n";
		return 0;
	}

	while (!result.empty())
	{
		if (result.front())
		{
			cout << "+\n";
		}
		else
		{
			cout << "-\n";
		}
		result.pop();
	}
}

---

 

sequence: 입력받은 수열을 담는 벡터입니다.

outputStack: 스택에 채워넣을 숫자 1부터 n까지를 보관하는 스택입니다.

inputStack: 문제에서 제시한 오름차순으로 숫자를 채워넣기위한 스택입니다.

result: 수열 생성이 불가능한 경우에 "NO" 메시지만 출력해야하기 때문에 프린트할 문자 +, -를 큐에 저장해 놓습니다.