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

http://acmicpc.net/problem/1874

{코드}

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

int main()
{
    int n, num, cur = 1;
    stack<int> s;
    string ans = "";
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        if (num >= cur)
        {
            while (num + 1 != cur)
            {
                s.push(cur++);
                ans += "+\n";
            }
            s.pop();
            ans += "-\n";
        }
        else
        {
            if (s.top() == num)
            {
                s.pop();
                ans += "-\n";
            }
            else
            {
                ans = "NO";
                break;
            }
        }
    }
    cout << ans;

    return 0;
}

{설명}

스택에 들어가는 수들은 1부터 차례로 들어가기 때문에 다음에 들어갈 수를 cur라는 변수에 저장한다.

+와 -는 push일때 +를 추가하고 pop일때 -를 추가한다.

중요한 점은 하나라도 그냥 pop해서는 안된다는 것이다. 주어지는 정수 모두 스택에서 pop없이 해당 수가 스택의 맨 위에 있도록 할 수 있어야 한다.

만약 입력받은 수가 cur보다 크거나 같으면 cur부터 해당 수까지 스택에 저장하고 이때 스택의 맨 위에는 입력받은 수가 저장되어 있으므로 이를 pop한다.

만약 입력받은 수가 cur보다 작다면 그 수가 스택의 맨 위에 있지 않다면 pop을 해야하기 때문에 ans를 NO로 바꾸고 반복문에서 나온다.