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

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

문제의 설명을 바로 이해하지 못했는데 간단하게 말하면 다음과 같다.

1부터 입력된 N까지 수를 스택에 넣을건데, 2번째 줄부터 입력된 수부터 차례대로 POP해서 스택에 모든 값들이 빠지는 지 확인하는 것이다.

---

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

using namespace std;

int main()
{
	vector <char> ans;
	stack <int> stack;
	int N;
	int value = 1;
	bool clear = true;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;

		while (value <= input)
		{
			stack.push(value);
			value++;

			ans.push_back('+');
		}

		if (stack.top() == input)
		{
			stack.pop();
			ans.push_back('-');
		}
		else
			clear = false;
	}

	if (clear)
	{
		for (char ch : ans)
			cout << ch << '\n';
	}
	else
		cout << "NO" << endl;

	return 0;
}

어차피 NO가 뜰 경우는 입력된 수가 이전에 들어가서 스택의 TOP값이 입력값보다 높은 경우밖에 없다.

그러므로 입력을 하나씩 받으면서 그 수가 나올 때 까지 스택에 넣는 작업을 수행한다.

넣은 후 맨 위와 비교해서 맞으면 빼주고 그렇지 않으면 불가능한 수열이기 때문에 clear를 false로 바꿔준다.

 

마지막에는 clear 변수에 따라 ans에 들어가있는 요소를 출력하거나 NO를 출력해주면 된다.