[알고리즘/C++] 백준 1874. 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

STL 연습겸 STL stack으로 풀긴 했지만 배열이 더 효율적일 듯한 문제.

1부터 n까지의 숫자가 순서대로 들어온다고 하니, 크게 답변 출력을 위한 문자 stack과 값 저장을 위한 int형 stack 두개를 선언한다.

int형 변수를 하나 선언해서 그거보다 큰 값이 들어오면 같아질때까지 stack에 push 후, 같아지면 pop하는 식으로 구현한다.

들어온 숫자가 int변수보다 작은 경우는 두가지일 것이다. top에 있어서 수열로 만들 수 있거나, 아니면 top에 없으므로 수열로 구현 불가능하거나.

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

int main() {
	// your code goes here
	stack<int> in;
	stack<char> ans, ans_;
	int a;
	cin >> a;
	
	for(int i = 0, j = 0 ; i < a ; i++){
		 int b;
		 cin >> b;
		 if(b > j){
		 	while(b != j){
		 		in.push(++j);
		 		ans.push('+');
		 	} 
		 }
		 if(b == in.top()){
		 	in.pop();
		 	ans.push('-');
		 }
		 else{
		 	cout << "NO";
		 	return 0;
		 }
	}
	
	
	while(!ans.empty()){
		ans_.push(ans.top());
		ans.pop();
	}
	while(!ans_.empty()){
		cout << ans_.top() << "\n";
		ans_.pop();
	}
	return 0;
}