[백준] 스택 수열(1874)

스택을 사용해서 푸는 간단한 문제이다!!...

1~n까지의 수를 push, pop을 해서 예제 입력에 넣는 수열을 만들 수 있는지 없는지를 판별하는 문제이다.

만약 만들 수 있다면 push, pop연산의 순서를 출력하고 만들 수 없다면 NO를 출력하면 된다.

 

이 문제에서 주의할 점은 empty인 상태에서 top의 값을 확인하려고 시도하는 것이다.

empty인 상태에서 top의 상태를 확인할 수 없다.

만약 empty라면 push를 해주자.

 

마지막까지 push를 하고 만약 지금 원하는 값과 스택의 top값이 다르다면 불가능한 경우로 판단하고 NO를 출력한다.

 

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

int arr[100001];
stack<int> st;
queue<int> q;

int main(void)
{
	
	int n = 0;
	cin >> n;

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

	int k = 1;
	int sig = 0;

	for (int i = 0; i < n; i++)
	{
		while (true)
		{
			if (st.empty())
			{
				st.push(k);
				k++;
				q.push(1);
			}
			if (k > n)
			{
				if (arr[i] != st.top())
				{
					sig = 1;
					break;
				}
			}
			if (arr[i] != st.top())
			{
				st.push(k);
				k++;
				q.push(1);
			}
			else
			{
				st.pop();
				q.push(0);
				break;
			}
		}
	}

	if (sig == 1)
	{
		cout << "NO";
	}
	else
	{
		while (!q.empty())
		{
			int num = q.front();
			q.pop();
			if (num == 0)
			{
				cout << '-' << '\n';
			}
			else
			{
				cout << '+' << '\n';
			}
		}
	}

	return 0;
}