[백준] 1874 스택 수열 - C++

문제) 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 푸시와 팝 연산을 수행해야 하는지 알려주는 프로그램을 만들어보자.

    첫줄에 n까지의 수 n이 주어진다. 둘째 줄 부터는 수열을 이루는 수가 순서대로 주어진다. 푸시는 +, 팝은 -, 불가능 할 때는 NO를 출력하면 된다.

    시간 제한은 2초, 메모리 제한은 128MB 이다.

 

스택을 알고 있으면 쉽게 풀 수 있는 문제다. 스택에 넣는 값은 오름차순으로 주어지니 그것만 생각하면 된다.

 

i는 0부터 n까지
    현재 수열값이 오름차순한 자연수 값 이상이라면
        값이 같아질때까지 푸시
        마지막 값을 팝
    아니라면
        팝한 값이 수열의 수보다 크다면
            NO 출력

 

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

using namespace std;
typedef pair<int, int> Node;

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

	int n;
	cin >> n;

	vector<int> a(n, 0);
	vector<char> resVec;

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

	stack<int> stk;

	int num = 1;
	bool result = true;

	for (int i = 0; i < a.size(); i++)
	{
		int now = a[i];

		if (now >= num)
		{
			while (now >= num)
			{
				stk.push(num++);
				resVec.push_back('+');
			}
			stk.pop();
			resVec.push_back('-');
		}
		else
		{
			int n = stk.top();
			stk.pop();
			if (n > now)
			{
				cout << "NO";
				result = false;
				break;
			}
			else
			{
				resVec.push_back('-');
			}
		}
	}

	if (result)
	{
		for (int i = 0; i < resVec.size(); i++)
		{
			cout << resVec[i] << '\n';
		}
	}

	return 0;
}