본문 바로가기

Programming/BOJ

[백준/C++] 1874번: 스택수열

 

while문을 돌릴 때 2개의 변수를 사용하였다. (stack에 넣어줄 숫자를 나타내는 num과 현재 target으로 하는 숫자를 가리키는 start변수)

1. top과 target이 같으면 pop하고 아니면 push한다.

2. 종료조건은 start가 target의 마지막 방을 가리킬 때 혹은 지금 num이 target숫자보다 클 때

 

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

int main() {

	int N; cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++) {
		int temp; cin >> temp;
		v.push_back(temp);
	}


	stack<int> s;
	vector<char> oper;
	int num = 1;
	int start = 0;
	while (1) {

		if (start >= N) break; //종료조건 1

		if (s.empty()) {
			s.push(num);
			oper.push_back('+');
			num++;
		}

		else {
			if (s.top() > v[start]) break; //종료조건 2
			if (s.top() == v[start]) {
				s.pop();
				oper.push_back('-');
				start++;
			}
			else {
				s.push(num);
				oper.push_back('+');
				num++;
			}
		}

	}

	if (!s.empty()) cout << "NO";
	else {
		for (int i = 0; i < oper.size(); i++) {
			cout << oper[i] << "\n";
		}
	}


	return 0;
}