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

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

int main()
{
	ios::sync_with_stdio(false);

	vector<int> num;
	stack<int> stacks;
	int n, m, count = 1;
	string result;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> m;
		num.push_back(m);

		while (num[i] >= count)	//받은 m 값에 도달할때까지 push
		{
			stacks.push(count);
			result += '+';
			count++;
		}
		if (stacks.top() == num[i])	//받은 값이 top일때 pop
		{
			stacks.pop();
			result += '-';
		}
		else	//받은 값에 도달못하면 no
		{
			cout << "NO";
			result = '0';
			break;
		}
	}
	
	if (result != "0")	//모두 완료일때만 출력
	{
		for (int i = 0; i < result.size(); i++)
		{
			cout << result[i] << "\n";
		}
	}

	return 0;
}

 

문제를 이해하는 것이 어려웠지만 풀 수 있었다.

 

1번예시

• 값이 4 3 6 8 7 5 2 1 이므로
• 스택에서는 1 2 3 4 순으로 입력이 된다. (오름차순)
• 그러면 4에 도달했으므로 pop후에  i증가
• 값이 3에 도달했으므로 pop
• num[2]는 6이므로 6이될때까지 push
• 1 2 5 6 
• 6도달했으므로 pop 후에 i증가
• 다시 1 2 5에서 push
• 1 2 5 7 8
• 목표값인 8 7 5 2 1순으로 pop계속되고 마무리 된다.

2번예시

• 값 1 2 5 3 4
• 1push 1pop
• 2push 2pop
• 3 4 5 push
• 5pop
• 다음 수인 3을 pop해야하지만 top이 4이므로 NO가 된다.