[BOJ] 1874 - 스택 수열

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

---

[알고리즘풀이]

1. 현재 스택의 Top보다 큰 값이 들어온다면, 그 수까지 스택을 Push하고 Push한 수들은 check를 한다.

  ( 이미 Push했던 수들은 다시 Push하면 안되므로 )

2. 현재 스택의 Top과 같은 값이 들어온다면, 스택을 Pop한다.

3. 현재 스택의 Top보다 작은 값이 들어온다면, "NO"를 출력한다.

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int list[100001];
bool c[100001];
stack<int> s;
string answer;

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

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++){
		cin >> list[i];
	}

	s.push(0);

	for (int i = 1; i <= n; i++) {
		if (s.top() == list[i]) {
			s.pop();
			answer += '-';
			continue;
		}
		if (s.top() < list[i]) {
			for (int j = s.top() + 1; j <= list[i]; j++){
				if(c[j] == false){
					s.push(j);
					c[j] = true;
					answer += '+';
				}
			}
			s.pop();
			answer += '-';
			continue;
		}
		if (s.top() > list[i]) {
			cout << "NO\n";
			return 0;
		}
	}
	for (int i = 0; i < answer.length(); i++)
		cout << answer[i] << '\n';
}

---