[백준] 1874번 스택 수열 (C++)

문제

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

---

풀이

stack과 queue를 이용하여 해당 문제를 풀이했다.

 

1. 처음 입력 받은 수를 queue에 저장한다.
2. 1부터 stack에 저장하고 queue의 front() 값과 비교하여 같지 않을 때까지 stack과 queue의 값을 pop한다.
3. n까지 2번을 반복한다.

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

using namespace std;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	queue <int> q;
	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		q.push(input);
	}

	vector <char> answer;
	stack <int> stack;
	for (int i = 1; i <= n; i++) {
		stack.push(i);
		answer.push_back('+');

		while (true) {
			if (stack.empty() || q.empty() || stack.top() != q.front()) break;

			q.pop();
			stack.pop();
			answer.push_back('-');
		};
	}

	if (!q.empty())
		cout << "NO";
	else {
		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i] << "\n";
		}

	}

	return 0;
}