백준 1847 스택 수열

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 수열을 입력받고 이러한 수열을 스택을 이용해서 나타낼 수 있다면 push와 pop을 어떻게 진행해야 하는지 출력하고 그럴 수 없다면 NO를 출력하는 문제입니다. 이때 스택에 push는 반드시 1부터 n까지 순서대로만 들어 갈 수 있습니다.

 

따라서 저는 pushnum이라는 변수를 선언해 어떤 숫자까지 push가 되었는지 체크를 하였습니다. 

 

처음에는 우선 수열의 맨처음 숫자만큼 스택에 push가 됩니다. 저는 +/-기호는 벡터에다가 저장해 두었습니다. 

 

맨처음 숫자만큼 push를 하고 push를 마치고 나면 첫번째 숫자는 나와야 하므로 pop을 해줍니다. 그리고 두번째 수열의 숫자부터는 스택의 top부분과 비교를 하여 top과 숫자가 동일하다면 pop을 해주고 top보다 큰 숫자라면 그만큼 더 push를 해주고 만일 top보다 작은 숫자가 나온다면 이는 만들어 질 수 없는 수열이므로 NO를 출력하도록 코드를 작성하였습니다.

 

다음은 코드입니다.

 

 #include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int arr[100001] = {0, };
	int n;
	stack<int> s;
	vector<char> v;
	bool flag = true;
	int pushnum = 0; 
	 
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	for(int i = 0; i < n; i++) {
		
		if(!s.empty() && s.top() == arr[i]) {
			s.pop();
			v.push_back('-');
			continue;
		}
		
		else if(!s.empty() && s.top() > arr[i]) {
			flag = false;
			break;
		}
		
		for(int j = pushnum; j < arr[i]; j++) {
			pushnum++;
			s.push(j+1);
			v.push_back('+');
		}
		v.push_back('-');
		s.pop();
	}
	
	if(flag) 
		for(auto n: v)
			cout<<n<<'\n';
	else
		cout<<"NO";	
	return 0;
}