백준 1874 cpp // 유효스택검사 알고리즘

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

1874번: 스택 수열

* 정처기 단골문제

: 다음 중 stack 의 출력결과로 나올수없는것은? 문제와 유사하다.

 

* 1씩 증가 구현방법

해결 : int cnt++ 

벡터나 배열로 구현할 필요가 없다.

 

*의사코드

1. while(n--) // 모든타겟에대해

2. while(cnt <= target) push(cnt++) ,"+"

3. top != target -> 불가능 , 끝내기

4. 가능하면, pop, "-"

ex) targets = 3 1 2

push 1 2 3

pop 3

2 !=1 이므로 불가능하다.

#include<bits/stdc++.h>
using namespace std;

int n;
stack<int> s;
string ret;
int cnt = 1;

void print_q(queue<int> q) {
	while (q.size()) {
		cout << q.front()<<" ";
		q.pop();
	}
	cout << endl;
}
void print_s(stack<int> s) {
	while (s.size()) {
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
}
int main() {
	cin >> n;
	
	while (n--) {
		int target;
		cin >> target;
		while (cnt <= target) {
			ret += "+\n";
			s.push(cnt++);
		}

		if (s.top() != target) {
			cout << "NO";
			return 0;
		}
		ret += "-\n";
		s.pop();
	}

	cout << ret;
}