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

#접근 방법 

 

먼저, 임의의 수열을 만들기 위해 N을 입력받고 N만큼의 수를 입력받는다. 

본인은 하나의 입력값을 입력할 때 바로 Stack을 활용했다. 

 

1. 스택이 현재 비어있지 않고 top 이 입력받은 수라면 pop 하고 '-' 추가

2. number의 현재 값이 입력받은 값보다 작다면 같을때까지 스택에 (number++)  push 와 '+" 추가 

3. 스택이 현재 비어있지 않고 top이 입력받은 수보다 크다면 바로 "NO" 출력 후 종료 

->  "반드시 오름차순을 지키도록 한다"조건때문에 top 이 입력받은 수보다 크다는 것은 해당수열을 만들수 없다는 것을 의미. 만들수 있었으면 조건 1에서 바로 pop 되어지기때문. 

 

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std; 
int main() {
	
	stack <int> st; 
	int n; cin >> n; 
	vector <char> answer; 
	vector <int> input(n); 
	int number = 1; 
	for (int i = 0; i < n; i++) {
		int a; cin >> a; 
		if (!st.empty() && st.top() == a) {
			st.pop(); 
			answer.push_back('-'); 
		}
		else if(number<=a) {

			while (number <= a) {
				st.push(number++);
				answer.push_back('+'); 
			}
			st.pop(); 
			answer.push_back('-'); 
		}
		else if (!st.empty() && st.top() > a) {
			cout << "NO"; 
			return 0; 

		}
		
	}
	for (auto x : answer) {
		cout << x << "\n"; 
	}
	return 0; 

}

 

1874번: 스택 수열