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

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

1874번: 스택 수열

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int main()
{
	int n;
	int check;
	int arr[100001];
	string str1 = "push";
	string str2 = "pop";
	cin >> n;
	queue<int> q;
	queue<string> q_s;
	stack<int> s;
	for (int i = 0;i < n;i++)
	{
		int element;
		cin >> element;
		q.push(element);
		arr[i+1] = 1;
	}

	for (int i = 0;i < q.front();i++)
	{
		s.push(i+1);
		q_s.push(str1);
	}

	arr[s.top()] = 0;
	q.pop();
	s.pop();
	q_s.push(str2);
	
	while (1)
	{
		if (q.size() == 0)
		{
		check = 1;
		break;
		}

		else if (s.size()==0)
		{
			for (int i = 1;i <= q.front();i++)
			{
				if (arr[i] == 1)
				{
					s.push(i);
					q_s.push(str1);
					arr[i] = 0;
				}
			}
		}
		
		else if (q.front() > s.top())
		{
			while (q.front() != s.top())
			{
				for (int i = s.top()+1;i <= q.front();i++)
				{
					if (arr[i] == 1)
					{
						s.push(i);
						q_s.push(str1);
						arr[i] = 0;
					}
				}
			}
		}

		else if (q.front() == s.top())
		{
			q_s.push(str2);
			arr[s.top()] = 0;
			q.pop();
			s.pop();
		}

		else
		{
			check = 0;
			break;
		}
	}
	if (check == 1)
	{
		while (q_s.size() != 0)
		{
			if (q_s.front() == "push")
			{
				cout << '+' << '\n';
				q_s.pop();
			}

			else
			{
				cout << '-' << '\n';
				q_s.pop();
			}
		}
	}

	else
		cout << "NO";

}

마무리 : 이 문제를 n까지 큐에 push하고 스택은 입력된 수열에 저장하여 비교하는 식으로 소스 코드를 짰는데 다른 사람 것과 비교하면 비효율적으로 짰다는 것을 할 수 있다. 만약 이 글을 본다면 이렇게 짜지 않았으면 한다.