백준 1874 스택 수열

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

1874번: 스택 수열

 

#include <iostream>
#include <stack>

using namespace std;

bool check[100000] = { false };
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	stack<int> sta;
	string out;
	sta.push(0);
	int num;
	cin >> num;

	bool clear = true;
	for (int i = 0; i < num; i++)
	{
		int st;
		cin >> st;

		if (sta.top() < num)
		{
			for (int j = sta.top(); j < st; j++)
			{
				if (check[j] == false)
				{
					out += '+';
					sta.push(j + 1);
					check[j] = true;
				}
			}
		}

		if (sta.top() == 0)
		{
			cout << "NO";
			clear = false;
			break;
		}

		if (sta.top() != st)
		{
			out += '-';
			sta.pop();
		}
		out += '-';
		sta.pop();
	}

	if (clear)
	{
		for (int i = 0; out[i] !='\0'; i++)
		{
			cout << out[i] << "\n";
		}
	}

}

 

 

문제가 어렵게 생각되는데 간단하다 값을 순서대로 ' + ' 하면서 나올 값을 ' - '하면 된다.

 

위 그림과 같이 예시를 예로들면 처음 4를 처리하기 위해 1,2,3,4를 ' + ' 하고 4를 ' - '했다. 그리고 다음 3은 ' + ' 가 필요없어 ' - ' 한 번 하고 끝났다. 다음 6은 이미 3과 4가 사라져서 5와 6을 ' + ' 하고 6을 ' - ' 했다. 이렇게 모든 번호를 처리하면 된다.