스택 수열 (feat. 백준, 1874번)

스택 수열
https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	stack<int> ans;
	queue<int> tmp;
	vector<char> words;
	cin >> N;
	for (register int n = 0, v; n < N; ++n)
		cin >> v, tmp.push(v);
	register int index = 1;
	while (!tmp.empty()) {
		if (index > (N + 1))
			break;
		if (ans.empty() || ans.top() != tmp.front())
			ans.push(index++), words.push_back('+');
		else if (ans.top() == tmp.front())
			ans.pop(), tmp.pop(), words.push_back('-');
	}
	if (!ans.empty() || !tmp.empty())
		cout << "NO" << "\n";
	else
		for (auto& word : words)
			cout << word << "\n";
	return 0;
}
// *&)*@*

1. 1부터 8까지 순서대로 스택에 push 또는 pop을 했을 경우, 문제로 주어진 순서대로 출력을 할 수 있는가 를 묻는 문제입니다.
2. 따라서 순서대로 출력할 수 있다면 1부터 8을 저장한 공간이 비어야 정상입니다. (모든 push, pop 과정이 이루어지므로)
3. 하지만 공간이 비어있지 않거나 8을 초과한 값까지 비교가 이루어진다면 스택 수열을 만들 수 없는 것이므로 'NO'를 출력합니다.