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

오늘은 백준1874번 스택 수열 문제를 풀어보도록 하자.

스택을 이용하여 주어진 입력의 수열이 나오면 push, pop의 연산이 어떻게 나오는지 출력하고 만일 나오지 않는다면 NO를 출력하는 문제이다.

문제는 다음과 같다.

                               [접근법]

  1. 벡터에 수열을 입력해놓고 하나하나씩 비교해보며 하면 된다.

  2. 만일 v[idx]의 값이 s.top()과의 값이 다르면 그냥 push('+')하고 같다면 pop('-')하면서 answer벡터에 저장한다.
  
  3. 연산을 다 마친 후 stack에 값이 남아있으면 수열을 만들지 못했다는 이야기. 즉, empty만 판별해주면 된다.

                                     [코드]
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	stack<int>s;
	int N, idx = 0;

	cin >> N;
	vector<int>v(N);
	vector<char>answer;

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

	for (int i = 1; i <= N + 1; i++) {
		while (!s.empty()) {
			if (v[idx] == s.top()) {
				s.pop();
				answer.push_back('-');
				idx++;
			}
			else {
				break;
			}
		}
		if (i == N + 1) {
			break;
		}
		s.push(i);
		answer.push_back('+');
	}
	if (!s.empty()) {
		cout << "NO" << '\n';
		return 0;
	}
	else {
		for (int i = 0; i < answer.size(); i++) {
			cout << answer[i] << '\n';
		}
	}
	return 0;
}