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

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

풀이

입력받는 정수 X에 대하여 수열을 만드는 규칙을 만족하는지 알아보자.

1부터 n까지의 수를 스택에 오름차순으로 push 하고, pop 하는 순서대로 수열이 만들어지기 때문에
스택의 top 요소와 X를 비교하면 수열을 만들 수 있는지 아닌지를 판단할 수 있다.

1. top < X
   X가 4이고, top 요소가 3이라고 하자. 4를 top 요소로 만들기 위해서는 4를 push 하면 된다.
   따라서 top 요소가 X보다 작다면, (마지막으로 push 된 수 + 1)부터 X까지 스택에 push 한다.

2. top == X
   X가 수열의 top 요소이므로 수열을 만들 수 있고, pop 한다.

3. top > X
   X가 3이고, top 요소가 4라고 하자. 스택에서 3을 pop 할 수 있는 시점은 top 요소인 4를 pop 한 이후이다.
   따라서 top 요소가 X보다 크다면, 수열을 만들 수 없다.

즉, X가 수열의 top 요소가 될 수 있다면 수열을 만들 수 있고, 그렇지 않다면 수열을 만들 수 없다.

---

코드로 구현할 때, 스택이 비는 경우가 발생하지 않도록 처음에 스택에 0을 push 하였다.
그리고 수열을 만들 때 push, pop 연산을 저장하기 위한 vector를 선언하고 해당 연산을 할 때마다 '+', '-'를 삽입하였다.

코드

#include <bits/stdc++.h>
using namespace std;

stack<int> s;
vector<char> v;
int cnt = 1;

bool isValid(int input) {
    while(s.top() < input) {
        s.push(cnt++);
        v.push_back('+');
    } 

    if(s.top() == input) {
        s.pop();
        v.push_back('-');
    }

    if(s.top() > input) {
        cout << "NO";
        return false;
    }

    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;
    
    s.push(0);
    
    for(int i=0; i<n; i++) {
        int input;
        cin >> input;
        if(!isValid(input)) return 0;
    }

    for(auto e : v) cout << e << "\n";
    
    return 0;
}