[백준 C++] 1874 스택 수열 - 자료구조

1874번: 스택 수열

 

cpp

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

int main()
{
‌bool possible = true;

‌int n = 0;
‌cin >> n;

‌vector<int> sequence;
‌sequence.reserve(n);
‌for (int i = 0; i < n; ++i)
‌{
‌‌int inputNumber = 0;
‌‌cin >> inputNumber;
‌‌sequence.emplace_back(inputNumber);
‌}

‌stack<int> outputStack;
‌for (int i = n; i > 0; --i)
‌{
‌‌outputStack.push(i);
‌}

‌queue<bool> result;
‌stack<int> inputStack;
‌for (int i = 0; i < n; ++i)
‌{
‌‌while ((inputStack.empty() || inputStack.top() < sequence[i])
‌‌‌&& !outputStack.empty())
‌‌{
‌‌‌inputStack.push(outputStack.top());
‌‌‌outputStack.pop();
‌‌‌result.push(true);
‌‌}

‌‌if (inputStack.top() == sequence[i])
‌‌{
‌‌‌inputStack.pop();
‌‌‌result.push(false);
‌‌‌continue;
‌‌}
‌‌else
‌‌{
‌‌‌possible = false;
‌‌‌break;
‌‌}
‌}

‌if (!possible)
‌{
‌‌cout << "NO\n";
‌‌return 0;
‌}

‌while (!result.empty())
‌{
‌‌if (result.front())
‌‌{
‌‌‌cout << "+\n";
‌‌}
‌‌else
‌‌{
‌‌‌cout << "-\n";
‌‌}
‌‌result.pop();
‌}
}

---

 

sequence: 입력받은 수열을 담는 벡터입니다.

outputStack: 스택에 채워넣을 숫자 1부터 n까지를 보관하는 스택입니다.

inputStack: 문제에서 제시한 오름차순으로 숫자를 채워넣기위한 스택입니다.

result: 수열 생성이 불가능한 경우에 "NO" 메시지만 출력해야하기 때문에 프린트할 문자 +, -를 큐에 저장해 놓습니다.