[C/C++] 백준 #1874 스택 수열(스택)

이번 문제는 스택에 대해서 잘 이해를 해야 합니다.

 

N의 숫자가 주어지고, 스택이 하나 주어졌을때, 1부터 N까지의 숫자를 차례로 스택에 Push할 수 있고, 스택이 비어있지 않는다면, 언제든 Pop을 한다고 했을 때, 우리는 1부터 N까지의 숫자가 한번씩 사용이 된 수열을 얻게 됩니다.

 

예를 들어서 Push 1, Push 2, Push 3, Push 4, Pop, Pop 을 하면, 4와 3이 출력되게 되고, Push 5, Push 6, Pop 하면 6을 출력하게 됩니다.  Push 7, Push 8, Pop, Pop, Pop, Pop, Pop, Pop 하게 된다면, 8, 7, 5, 2, 1 이 나오게 되어 최종적으로 4, 3, 6, 8, 7, 5, 2, 1 이라는 수열을 얻게 됩니다.

 

이번 문제는 바로 이 스택 수열을 이용해서 어떠한 스택 연산을 했는지를 찾는 것입니다.

 

바로 우리가 스택 수열을 얻기 위한 작업을 그대로 따라하면 될 것입니다.  현재 스택이 비어있는 상태에서 Push해야할 순서의 숫자를 1이라고 지정합니다.  4가 나오기 위해서는 4까지의 숫자까지  Push가 이루어져야합니다.  만약, 현재 Push해야할 숫자가 출력해야할 숫자보다 크고, 스택의 맨 위의 숫자가 해당 숫자가 아니라면, 이 수열을 스택 수열이 아닙니다.  현재 Push해야할 순서는 1이므로 4가 들어갈 때까지 숫자를 스택에 Push합니다.  스택에는  [ 1, 2, 3, 4 ]가 들어가있고, Push는 4번 이루어졌습니다.  Push(#4), 4를 출력해야 하므로 Pop을 합니다.  그러면 스택에는 [ 1, 2, 3 ]이 남아있습니다.  다음에 출력되어야 하는 수는 3이므로 또 Pop을 합니다.  스택에는 [ 1, 2 ]가 남아있습니다.  다음 출력해야하는 숫자는 6이므로 2번의 Push를 합니다.  스택은 [ 1, 2, 5, 6 ] 입니다.  그 후 Pop을 합니다.  스택은 [ 1, 2, 5 ]가 됩니다.  다음은 8을 출력해야하므로 2번 Push를 합니다.  [ 1, 2, 5, 7, 8 ] 스택 상태에서 Pop을 하면 스택은 [ 1, 2 5, 7 ]이 됩니다.  다음은 7, 5, 2, 1 순이므로 그대로 4번의 Pop을 하면 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------
//    baekjoon #1874
//        - by Aubrey Choi
//        - created at 2019-05-23
//------------------------------------------------
#include <stdio.h>

int main()
{
    int stack[100000];
    char result[200000];
    int n, pushed = 1, sp = 0, rp = 0;

    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int c;
        scanf("%d", &c);
        while(pushed <= c)
        {
            stack[sp++] = pushed++;
            result[rp++] = '+';
        }
        if(sp <= 0 || stack[sp - 1] != c)
        {
            puts("NO");
            return 0;
        }
        sp--;
        result[rp++] = '-';
    }
    for(int i = 0; i < rp; i++)
        printf("%c\n", result[i]);
}