[c++] 1874번 스택 수열

 

 

정답코드

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


int main()
{
	int cnt = 1;
	int n;
	cin >> n;
	stack<int> s;
	vector<char> result;


	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;

		while(cnt <= x)
		{
			s.push(cnt);
			cnt += 1;
			result.push_back('+');
		}

		if(s.top() == x)
		{
			s.pop();
			result.push_back('-');
		}
		else
		{
			cout << "NO";
			return 0;
		}
	}

	for(int i=0; i < result.size(); i++)
	{
		cout << result[i] << '\n';
	}
	return 0;
}

스택을 이용하여 해결하면 됩니다.

 

여기서 마지막 vector를 출력해낼 때 endl을 사용할 경우 버퍼를 계속해서 플러시하면서 시간 초과가 발생할 수 있으니 \n으로 바꾸어주면 됩니다.

 

알고리즘은 s.top이 x가 아니라면 계속해서 + 를 해주면 되기에 result에 +를 pushback 해주고 만약 top 즉 맨 최근에 들어온 스택에서의 상단의 값이 x라면 - 즉 pop을 해줘야 하기 대문에 pop을 해준 다음 result에 -를 push_back 해줍니다.