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

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

 

해설

숫자가 오름차순으로 주어지고 오름차순으로 주어지는 수를 기반으로 입력으로 들어오는 수의 순서대로 수열을 만들 수 있는지 물어보는 문제이다.

4가 들어온다면 1 2 3 4를 스택에 넣고 pop을 해서 4를 만들 수 있고 3을 이어서 만들기 위해서 스택에서 바로 pop을 해서 3을 만들고 6을 만들기 위해서는 5 6을 스택에 집어 넣고 pop을 해서 6을 만들 수 있는지를 물어보는 문제.

 

현재 오름차순의 수를 추적할 수 있는 변수 num을 두고 num을 기준으로 입력의 수열대로 만들 수 있는지 확인하면된다.

코드를 보고 이해를 하도록 하자.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>
using namespace std;
using ll = long long;
#define endl "\n"

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n; cin >> n;
	vector<char> ret;
	stack<int> stk;
	int num = 1;
	for (int i = 0; i < n; ++i)
	{
		int a; cin >> a;
		while (num <= a)
		{
			ret.push_back('+');
			stk.push(num++);
		}
		if (stk.top() != a)
		{
			cout << "NO" << endl;
			return 0;
		}
		ret.push_back('-');
		stk.pop();
	}
	for (char c : ret) cout << c << endl;
	return 0;
}

우선 num을 기준으로 a보다 작거나 같을 때까지 while문을 돌면서 스택에 수를 넣는다. (정답을 출력하기 위한 ret도 채운다)

그리고 스택의 top이 a와 다르다면 NO를 출력하고 그렇지 않다면 pop을 수행해준다.

 

후기

처음에 문제를 이해하는데 시간이 좀 걸렸다. 무엇으로 부터 수열을 만드는지에 대해서 이해를 잘 못했었는데 여러번 읽어보니 이해가 되었다.

핵심은 num이라는 변수로 현재 오름차순의 수를 추적하는게 킥인거 같다