[백준] 1874 스택 수열 with C++

문제설명

---

입출력 예제

---

개념

　먼저 예제 1에 대해 스택 수열이 어떻게 형성되는지 그림으로 확인해 보자.

 

 

　그림에서 알 수 있듯이, 입력받은 수 n이 기존의 max보다 크다면 max + 1부터 n까지 스택에 수를 푸시한다. 그렇지 않다면, 입력받은 수가 스택에서 뽑을 때까지 pop을 해주면 된다.

 

　반대로 스택 수열을 형성할 수 없는 경우인 예제 2를 보자.

 

 

　3을 입력받는 순간 3을 뽑기 위해서 4를 뽑아야 하는데, 4를 빼면 주어진 수열을 만들 수 없으므로 에러가 뜬다. 즉, 입력받은 수가 num보다 작거나 같은데, 그 수가 스택의 top과 다르다면 주어진 수열을 만들 수 없다.

---

풀이

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

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n, num, max = 0;
	cin >> n;
	stack<int> st;
	vector<char> ans;

　문제에서 제시한 테스트 케이스의 개수 n, 입력받을 자연수 num, 최댓값 max를 초기화한다.

 

	while (n--)
	{
		cin >> num;

		if (num > max)
		{
			for (int i = max + 1; i <= num; ++i)
			{
				st.push(i);
				ans.push_back('+');
			}
		}

		else if (st.top() != num)
		{
			cout << "NO";
			return 0;
		}

		st.pop();
		ans.push_back('-');

		if (max < num)
			max = num;
	}

　자연수 num을 입력하고, 이 수가 max보다 크다면 그 수만큼 스택에 문자 '+"를 푸시해 준다. 만약 num <= max인데 스택의 top이 num과 다르다면 수열을 만들 수 없으므로 "NO"를 출력하고 종료한다.

　그 후 스택에서 문자를 하나씩 빼며 '-'를 푸시해준다.

 

	for (auto& val : ans)
		cout << val << '\n';
}

　모든 반복을 끝마치고 나서 ans 스택에서 문자를 하나씩 꺼내 출력한다.

 

총합본

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

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n, num, max = 0;
	cin >> n;
	stack<int> st;
	vector<char> ans;

	while (n--)
	{
		cin >> num;

		if (num > max)
		{
			for (int i = max + 1; i <= num; ++i)
			{
				st.push(i);
				ans.push_back('+');
			}
		}

		else if (st.top() != num)
		{
			cout << "NO";
			return 0;
		}

		st.pop();
		ans.push_back('-');

		if (max < num)
			max = num;
	}

	for (auto& val : ans)
		cout << val << '\n';
}