백준 1874번: 스택 수열

 

스택과 큐를 활용한 문제이다.

여러가지 예외만 잘처리해주면 쉬운 문제였다.

 

 

 

 

중요 포인트

1. 실행 중간에 불가능이 나오면 "NO"만 출력해야한다. 
2. 결과를 한번에 출력해야하는데 역순 출력이 아니므로 stack이 아닌 queue에 출력할 연산들을 담는다.
3. push되는 숫자는 1부터 오름차순이고, pop된 숫자는 다시 push 안됨. (push 되는 숫자를 따로 두지 않고 stack의 용량과 같은 값으로 두면 에러가남) 여기선 num으로 둔다.
4. s.top()과 inp을 비교햇을 때, top이 더 크면 불가능 (pop은 입력된 숫자와 같은 숫자만 가능하기때문)
5. s.top()이 inp값보다 작을 땐, 같거나 커질 때 까지 push(num) 해주는데 그때마다  num++; 한다.
6. 5번에서 크면 불가능, 같으면 pop한다.

 

 

 

 

 

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

int n;


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상


	stack<int> s;
	queue<string> t;
	cin >> n;

	int num = 1;
	bool possible = true;


	for(int i = 0; i < n; i++){
		int inp = 0;
		cin >> inp;


		if (!s.empty()) {
			if (s.top() > inp) {
				possible = false;
				break;
			}
				
		}
		
		
		while (s.empty()||s.top() < inp) {
			s.push(num);
			num++;
			t.push("+");
		}

		if (s.top() == inp) {
			s.pop();
			t.push("-");
		}
		else {
			possible = false;
			break;
		}
	}

	int p = t.size();
	if (possible) {
		for (int i = 0; i < p; i++) {
			cout << t.front() << "\n";
			t.pop();
		}
	}
	else
		cout << "NO" << "\n";

	return 0;
}