백준 1874 풀이

링크텍스트

'스택 수열'문제다.

문제 이름에서 알 수 있듯이 스택을 이용하면 쉽게 풀어낼 수 있다.

문제를 푸는데 큐와 스택, 벡터를 사용했다.

입력받은 숫자를 큐에 저장하고, 반복문을 돌면서 스택에 1부터 숫자를 쌓는다. 쌓으면서 현재 스택의 top과 큐의 front를 비교하면서 같으면 스택과 큐에서 팝을 하여 목록에서 제외해준다.

이와 같은 과정을 거치면서 연산자를 넣을 벡터에 push는 +, pop은 -를 저장해준다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
using namespace std;

int n;
int m;
long long arr[1001];


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;

	cin >> n;
	queue<int> v;
	stack<int> stack;
	vector<string> op;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push(tmp);
	}

	for (int i = 0; i < n; i++) {
		stack.push(i + 1);
		op.push_back("+");
		while (!v.empty() && !stack.empty() && v.front() == stack.top()) {
			stack.pop();
			v.pop();
			op.push_back("-");
		}
	}
	if (stack.empty()) {
		for (int i = 0; i < op.size(); i++) {
			cout << op[i] << '\n';
		}
	}
	else {
		cout << "NO" << '\n';
	}

	return 0;
}