백준 1874번 - 스택 수열

void_melody 2022. 6. 24. 13:29

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

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

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

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

	int n;
	cin >> n;

	stack<int> s;
	int cnt = 1;
	vector<char> v;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		while (cnt <= a)
		{
			s.push(cnt);
			cnt++;
			v.push_back('+');
		}
		if (s.top() == a)
		{
			s.pop();
			v.push_back('-');
		}
		else
		{
			cout << "NO";
			return 0;
		}
	}
	for(const auto& i : v)
		cout << i << '\n';
}