[C++] BaekJoon 1874 스택 수열

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

---

스택의 LIFO 특성을 이용하여 임의의 수열이 주어졌을 때 스택을 이용해 수열을 만들 수 있는지 알아내는 프로그램을 작성하는 문제이다. 

 

코드

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

using namespace std;

int main()
{
	int N;
	cin >> N;
	int C = 1; //카운터

	vector<int> s(N); //수열 
	stack<int> stack; //스택
	vector<char> o; //+,- 
	for (int i = 0; i < N; i++)
	{
		int M;
		cin >> M;
		if (!stack.empty() && stack.top() == M)
		{
			stack.pop();
			o.push_back('-');
		}
		else if (C <= M)
		{
			while (C <= M)
			{
				stack.push(C++);
				o.push_back('+');
			}
			stack.pop();
			o.push_back('-');
		}
		else if(!stack.empty() && stack.top() > M)
		{
			cout << "NO" << "\n";
			return 0;
		}
	}
	for (auto N : o)
	{
		cout << N << "\n";
	}
	return 0;
}

 

설명

 

수열의 길이를 N에 입력받는다. 

이를 입력 받아서 s라는 이름의 길이 N의 정수형 벡터를 생성한다.

이 벡터에 수열을 저장한다. 

 

N번 만큼 정수를 입력받고 입력 받은 수를 M에 저장하는데,

입력받은 수와 스택의 top을 비교하여 다음과 같은 조건에 따라 처리한다. 

 

if. 스택이 비어있지 않고, 스택의 top이 현재 입력된 수와 같다면 스택에서 pop하고 '-' 를 o 벡터에 저장한다. 

 

else if. 입력된 수가 현재 카운터 'C' 보다 크거나 같다면, 'C'부터 입력된 수까지 스택에 push 하고,

각각의 push 과정을 '+'로 o 벡터에 저장 한 뒤, 스택에서 pop하고 '-'를 o 벡터에 저장한다. 

이를 수행하는 이유는 C가 M이랑 같다면 스택에서 pop을 수행해야 하기 때문.

이후 C를 1 증가시킨다. 

 

else if. 스택이 비지 않고, 스택의 top이 현재 입력된 수보다 크다면 "NO"를 출력하고 프로그램을 종료. 

 

그 후 반복문을 통해 o 벡터에 저장된 값들을 출력.