백준 1874번: 스택수열

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

문제 접근

1. 정답 수열과 1 ~ n까지의 수열의 원소들을 비교한다.
2. 정답 수열의 원소(M)이 되기 전까지 스택에 1~n까지의 수열의 원소들을 집어 넣는다.
3. 같을 경우 push와 pop이 동시에 진행된다.
4. 작을 경우 스택의 탑을 확인한다. 이때 만약 동일하지 않으면 NO를 출력하고 종료시키면 된다.
5. while반복문을 빠져나오게 되었을때 스택의 원소들과 정답수열의 원소들을 하나씩 비교시킨다. 이 때 만약 다른게 있다면 NO를 출력하고 종료시킨다.

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

int main()
{
    int size;
    cin >> size;
    stack<int> s;
    vector<char> v;
    int *ans = new int[size];
    int *src = new int[size];
    for(int i = 1; i <= size; i++)
    {
        cin >> ans[i - 1];
        src[i - 1] = i;
    }
    int i = 0;
    int j = 0;
    while(j < size)
    {
        if(ans[i] > src[j])
        {
            s.push(src[j]);
            v.push_back('+');
            j++;
        }
        else if(ans[i] == src[j])
        {
            v.push_back('+');
            v.push_back('-');
            j++;
            i++;
        }
        else if(ans[i] < src[j])
        {
            if(ans[i] == s.top())
            {
                v.push_back('-');
                s.pop();
                i++;
            }
            else
            {
                cout << "NO" << '\n';
                return 0;
            }
        }
    }
    for(int k = i; k < size; k++)
    {
        if(ans[k] != s.top())
        {
            cout << "NO" << endl;
            return 0;
        }
        v.push_back('-');
        s.pop();
    }
    for(int x = 0; x < v.size(); x++)
    {
        cout << v[x] << '\n';
    }
    delete [] ans;
    delete [] src;
}