1874_스택 수열

▶실버2

풀이

스택을 사용하는 문제.

예제 1번을 예시로 들면,

① [0]: 4 > 1, 2, 3 ☞ (+): push

② [0]: 4 == 4 ☞ (-): pop

③ [1]: 3 == 3 ☞ (-): pop

④ [2]: 6 > 5 ☞ (+): push

⑤ [2]: 6 == 6 ☞ (-): pop

⑥ [3]: 8 > 7 ☞ (+): push

⑦ [3]: 8 == 8 ☞ (-): pop

→ n이 될 때까지 진행

따로 스택을 만들어서 그 스택의 top 값과 입력 값으로 주어진 값을 비교한다.

이때, top 값과 같다면 pop

top값이 더 크다면 NO를 출력하고 종료한다.

코드

#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

vector <int> v;
vector <char> ans;
stack <int> st;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}


	int x = 1;
	st.push(0);
	for (int i = 0; i < n; i++) {
		int tmp = v[i];
		while (1) {
			if (st.top() < tmp) {
				st.push(x++);
				ans.push_back('+');
			}
			int now = st.top();
			if (now < tmp) {
				continue;
			}
			else if (now == tmp){
				st.pop();
				ans.push_back('-');
				break;
			}
			else {
				cout << "NO" << endl;
				return 0;
			}
		}
	}
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << "\n";
	}
}