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

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

1874번: 스택 수열

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

int n;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;

	stack<int> s; 
	queue<int> q; // 큐는 수열 입력 받음
	string ans;   // +,- 로 이루어진 문자열 

	// 수열을 입력받는다
	while (n--)
	{
		int temp;
		cin >> temp;
		q.push(temp);
	}

	int index = 1; // 다음 스택에 들어갈 수

	// 반복문 탈출 조건은 큐가 다 비어졌을때 --> 순열이 완성됨을 뜻함
	while (!q.empty())
	{
		if (!s.empty())
		{
			// 스택과 큐의 top,front가 같지 않다면 스택에 뭔가 조치를 취해야한다
			if (s.top() != q.front())
			{
				// 보통의 경우에는 스택에 push를 더 해줘서 같게 해야한다
				// 그런데 스택에 push를 해서 더 이상 수열을 만들 수 없을때는 NO를 출력하고 프로그램 종료
				// 나는 다음 스택에 넣을 숫자가 큐의 맨 앞부분보다 크면이라고 조건을 설정
				// 만약 예제처럼 1, 2, 5, 3, 4 일때
				// push 1, pop 1, push 2, pop 2, push 3, push 4, push 5 , pop 5
				// 하면 다음 스택에 넣을 index는 6으로 설정되어있고 큐의 front는 3이다
				// 일단 숫자를 더 넣을 수 없다는건 알거고 현재 스택의 top은 4라서 어떤 조치를 취할 수 없기에
				// NO 출력후 리턴

				if (index > q.front())
				{
					cout << "NO";
					return 0;
				}
				s.push(index++);
				ans += '+';
			}
			// 현재 스택의 맨 위 부분이 큐의 맨 앞부분이 일치하면 스택,큐 pop
			else
			{
				s.pop();
				q.pop();
				ans += '-';

			}
		}
		else
		{
			// 스택이 비어있을때는 그냥 push 한다 -> 비어있을때 top을 방지하기 위해
			s.push(index++);
			ans += '+';
		}

	}

	int len = ans.size();

	for (int i = 0; i < len; i++)
		cout << ans[i] << '\n';

	return 0;
	
}

 

어 일단 내 생각을 코드안에 주석으로 써놓긴했는데 이게 남들한테는 이해가 잘 갈지 모르겠다 ㅋㅋ

NO를 출력하고 종료하는 그 조건만 잘 이해하면 쉬울 것 같다