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

 

알고리즘 분류: 자료 구조, 스택

문제 링크: https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

【 풀이 】

 

입력으로 받은 수열을 스택을 활용하여 순서대로 구현할 수 있는지를 물어보는 문제이다.

증가하는 변수 cnt를 선언해 주고, 입력한 숫자 n과 같아질 때까지 증가시키고 스택에 저장.

그 후 '+' 기호를 벡터에 저장한다.

그리고 스택의 맨 나중에 들어온 값과 입력 값이 일치하면  그 값을 빼내고

'-' 기호를 벡터에 저장.

 

여기서 입력값과 스택의 맨뒤의 값이 일치하지 않는다면 "NO"를 출력하면 된다.

 

 

 

【 코드 】

 

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

int main(void)
{
	vector<char>output;
	stack<int>seq;
	int n;
	int cnt = 1;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;

		while (cnt <= num)
		{
			seq.push(cnt);
			cnt++;
			output.push_back('+');
		}
		if (seq.top() == num)
		{
			seq.pop();
			output.push_back('-');
		}
		else
		{
			cout << "NO";
			return 0;
		}
	}
	for (int i = 0; i < output.size(); i++)
		cout << output[i] << '\n';
}