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

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

 

문제 분석

1부터 n까지의 수를 스택에 넣어놓고 입력받은 수열을 만들기 위해 push와 pop연산을 어떻게 수행해야 하는지 출력하는 문제다. push연산을 수행할 땐 +, pop연산을 수행할 땐 -를 출력한다. 입력받은 수열을 만들 수 없는 경우에는 NO를 출력한다.

 

 코드

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

int main(){
	cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
	
	vector<char> ans;
	stack<int> save;
	int cnt = 1;
	
	int n; cin>>n;
	int tmp;
	for(int i=0; i<n; i++){
		cin>>tmp;
		while(cnt<=tmp){
			save.push(cnt);
			cnt++;
			ans.push_back('+');
		}
		if(save.top() == tmp){
			save.pop();
			ans.push_back('-');
		}
		else{
			cout<<"NO";
			return 0;
		}
	}
	
	for(int i=0; i<ans.size(); i++) cout<<ans[i]<<"\n";
	
	return 0;
}

 

문제 풀이

1. 출력값들을 저장할 벡터 ans와 스택 save를 선언한다. 변수 cnt를 1로 설정한다.
2. 수들의 개수 n을 입력받고, 변수 tmp를 선언해 for문 안에서 tmp를 입력받는다.(수열)
3. cnt가 tmp보다 커질 때까지 while문으로 save에 cnt값을 push하고 push연산을 수행했으므로 ans에 +를 push한다. cnt는 while문이 돌 때마다 증가하도록 하여 같은 값이 들어가지 않도록 한다.
4. cnt가 tmp보다 크고 save의 top값이 tmp와 같다면 뽑아내서 수열로 만들어야 하므로 pop하고 pop연산을 수행했으므로 ans에 -를 push한다. 만약 save의 top값이 tmp와 다르다면 입력받은 수열을 만들 수 없다는 뜻이므로 NO를 출력하고 프로그램을 종료한다.
5. 수열을 만들 수 있다면 ans에 저장된 +, -들을 출력한다.