[BOJ] 1874번: 스택 수열

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

 

차분하게 스택의 동작을 따라가면 쉽게 풀리는 문제다.

케이스를 크게 3가지로 분류했다.

 

1. if stack.top() < target, then target이 나올 때까지 stack에 push

2. if stack.top() == target, then pop

3. if stack.top() > target, then IMPOSSIBLE

 

스택에는 1부터 n까지의 값이 차례로 쌓이기 때문에, 스택의 top에 있는 값이 target보다 이미 크다면 불가능한 수열이다.

 

코드는 아래와 같다.

/*
20200507
baekjoon 1874번 - 스택 수열
*/
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

int arr[100000]; vector<char>ans;
int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int n, last; bool found = true;
	cin >> n;
	stack<int>st;
	st.push(1); last = 1;
	ans.push_back('+');

	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; ++i) {
		if (st.empty() || st.top() <= arr[i]) {
			while (st.empty() || st.top() < arr[i]) {
				st.push(++last);
				ans.push_back('+');
			}
			ans.push_back('-');
			st.pop();
		}
		else {
			found = false;
			break;
		}
	}

	if (found) {
		for (auto i : ans) {
			cout << i << "\n";
		}
	}
	else {
		cout << "NO";
	}
}