[C++ / 1874] 스택 수열

문제

1874번: 스택 수열

---

문제 설명

스택의 특성에 따라 수열을 만들 것이다.

하지만 이 수열에 push 하는 순서는 반드시 오름차순을 지켜야 한다.

임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 판단하고, 어떤 순서로 push와 pop을 수행해야 하는지 알아내라.

---

풀이 방식

우선 문제의 이해가 조금 어려웠다.

예시를 들어 설명하자면, 예제의 size가 8인 스택에 수열을 push한다고 치자.

이때 4,3,6,8,7,5,2,1 이 순서대로 값을 입력할 것인데, 이때의 출력값이 + + + + - - + + - + + - - - - - 이고 작동원리는 다음과 같다.

 

우선 첫 입력값이 4이므로 스택에는 1, 2, 3, 4가 순서대로 값이 입력되고 4를 pop 해준다. 그래서 + + + + - 이다.

두번째 입력값은 3이다. 이때 스택에 1, 2, 3이 이미 들어가 있음으로 stack의 Top은 3이다.

그렇기에 값의 추가는 없고 3을 pop 해주기 때문에 - 이다.

세번째 입력값은 6이다. 스택에 1, 2가 들어가있고 4까지는 입력되었음으로, 5, 6을 추가적으로 스택에 넣은 뒤, 6을 pop 해준다.

그럼으로 6까지의 총 결과는 + + + + - - + + - 이다.

 

이런 규칙을 가지는 알고리즘을 구현하면 된다.

---

솔루션

#include <iostream>
#include <stack>
#include <vector>

using namespace std;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  stack<int> s;
  vector<char> result;

  int cur = 1;
  int n;
  cin >> n;

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

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

    if (s.top() == data)
    {
      s.pop();
      result.push_back('-');
    }

    else
    {
      cout << "NO";
      return 0;
    }
  }

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