[1874번] 스택 수열

1874번: 스택 수열

 

www.acmicpc.net

/*1874번 스택 수열*/
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
stack<int>S;
queue<char>Q;
int N, Arr_pointer = 0, push_num = 1;
int Arr[100000];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> Arr[i];
	while (Arr_pointer < N) {
		if (S.empty()) {
			S.push(push_num++);
			Q.push('+');
		}
		else {
			if (S.top() == Arr[Arr_pointer]) {
				S.pop();
				Arr_pointer++;
				Q.push('-');
			}
			else {
				if (S.top() > Arr[Arr_pointer]) {
					cout << "NO";
					return 0;
				}
				else {
					S.push(push_num++);
					Q.push('+');
				}
			}
		}
	}
	while (!Q.empty()) {
		cout << Q.front() << '\n';
		Q.pop();
	}
}

조건은 아래와 같다.

1. 스택에 1부터n까지 차례대로 들어간다. 스택에 쌓을 때는 +를 출력한다.

2. 스택의 top이 입력값과 같으면 pop을 하면서 -를 출력한다.

3. 입력값을 만들수 없으면 NO를 출력한다.

이 조건들을 이용해서 풀이과정을 적어보면,

1. 스택에 넣을 숫자를 선언해서 push때 만 값을 1씩 증가시킨다.

2. 입력값의 배열을 가르키는 포인터 변수를 선언해서 조건2에 부합하면 증가시킴

3. push, pop결과를 큐에 저장해서 조건 3에 부합하지 않고 반복문을 빠져나오면 큐에서 하나씩 뽑아서 출력한다.