[백준1874] 스택 수열

이 문제의 핵심은 스택에 들어가는 숫자는 감소하면 안된다는 것이다.

만약 이전에 스택에 1,2,3,4,5까지 넣은 적이 있다면 1,2,3,4,5보다 큰 숫자만 들어갈 수 있다.

즉 이미 뺀 숫자가 다시 들어갈 수 없다. 이 경우에는 "NO"를 출력한다. 

 

스택에서 가장 위에 있는 숫자가 지금 빼려는 숫자보다 작다면 빼려는 숫자가 될 때까지 더 숫자를 넣는다.

반대로 가장 위에있는 숫자가 지금 뺴려는 숫자보다 크다면 가장 위가 빼려는 숫자가 될 때까지 빼면 된다. 

즉, 지금 빼려는 숫자가 스택의 가장 위쪽에 있도록 만들어 준다. (push,pop을 통해)

주의할 점은 이미 넣었던 숫자는 다시 넣을 수 없다는 것이다. 따라서 지금까지 넣었던 숫자를 기억하기 위해 add변수를 추가한다.

넣으려는 숫자가 스택에서 빼려는 숫자(입력)보다 크다면 NO를 출력하고 프로그램을 종료했다. 

 

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
stack<int> s;
vector<int> vec;
int main() {
	int cnt;
	int tmp;
	int add = 0;
	scanf("%d", &cnt);
	s.push(0);
	for (int i= 0; i < cnt; i++) {
		scanf("%d", &tmp);
		if (s.top() < tmp) {//빼려는 숫자가 stack의 최상단보다 크면 넣었다가 뺴야한다.
			if (add >= tmp) {// 그러나 넣을 수 있는 숫자가 자기보다 크다면 stack 최상단에 해당 숫자가 있게 할 수 없다. 
				printf("NO");
				return 0;
			}
			while (s.top() != tmp) {
				add = add + 1;
				s.push(add);
				vec.push_back(1);
			}
		}
		else {
			while (s.top() != tmp) {
				s.pop();
				vec.push_back(0);
			}
		}
		int num = s.top();
		s.pop();
		vec.push_back(0);
	}
	for (int t = 0; t < vec.size(); t++) {
		if (vec.at(t) == 0) {
			printf("%s", "-\n");
		}
		else {
			printf("%s", "+\n");
		}
	}
}