1874)스택 수열

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

스택 수열은 주어진 수열을 push, pop해서 얻을 수 있는 수열을 말한다. 

다만 스택에 수열을 넣을 때는 오름차순으로 넣어야 한다.

예를들어 5이하의 자연수를 스택에 넣는다면 다음 그림처럼 1,2,3,4,5 순으로 넣어야 한다.

위와 같은 순서로 임의대로 push 와 pop 통해 만들어진 수열이 스택 수열이다.

문제는 N이하의 자연수로 push와 pop연산으로 주어진 스택수열을 만들어 낼 수 있는가 판단하는 것이다.

어떻게 주어진 수열이 스택 수열인지 판단할 수 있을까?

우선 top과 스택 수열의 첫 수를 비교한 뒤 같지 않으면 그 수와 같아질 때까지 1~N에서 차례대로 push한다.

스택 수열의 첫수와 top이 같아지면 같아지면 그 값을 pop한다.

push와 pop을 수행할 때마다 기록해둔다.

예를 들어 보자. 

스택 수열이 1,2,5,4,3이다.

1~5의 자연수로 위 스택 수열을 만들 수 있는지 판단해야 한다.

스택 수열의 첫 숫자는 1이다. 초기 스택의 top은 -1이다.

두 수가 다르기 때문에 1~5에서 첫 번째 수를 push한다.

top과 스택 수열의 첫 수가 같기 때문에 pop한다.

2도 똑같은 방식으로 움직이므로 3~5부터 동작시켜보자.

3을 넣고난 후 스택 수열의 세 번째 값인 5와 top을 비교했지만 같지 않다.

그래서 4를 넣는다.

4를 넣어도 스택 수열의 세 번째 값과 같지 않기 때문에 5를 넣는다.

5를 넣고 난 후에야 top과 스택 수열의 세 번째 값이 같다.

pop해서 5를 빼낸다.

이후엔 top과 스택 수열의 남은 수들이 차례대로 같으니 pop만으로 주어진 스택 수열을 만들 수 있다.

따라서 주어진 스택 수열 1,2,5,4,3은 스택 수열이다.

이제 경계 조건을 정해야 한다.

스택 수열을 만들려면 주어진 수들이 스택에 들어갔다가 나와야 한다.

즉 N번 반복한다.

그리고 스택 수열이 아닐 때 push와 pop연산은 배열 경계를 넘어서 접근하기 때문에

스택 수열이 아닌 경우의 경계 조건을 알아야 한다.

만들어야 할 스택 수열이 3,4일때 위 그림과 같은 스택의 상태로 3,4를 만들 수 있을까?

아무리 스택에서 수를 잘 꺼내봐야 4,3 순으로 나오기 때문에 3,4는 스택으로 만들 수 없는 수열이다.

여기서 발견할 수 있는 경계 조건은 top이 주어진 수보다는 크다는 점이다.

top이 주어진 수열의 수보다 크면 주어진 수열은 스택 수열이 아니기 때문에 push와 pop연산을 하면 문제가 생긴다.

그래서 간단한 장치를 만들어 push와 pop을 하지 못하게 해야 한다.

#include<stdio.h>
#include<stdlib.h>
 
#define TRUE 1
#define FALSE 0
 
struct STACK_NODE {
    int data;
    struct STACK_NODE *link;
};
 
struct STACK_NODE *top = NULL;
 
void push(int x) {
    struct STACK_NODE *newNode;
 
    newNode = (struct STACK_NODE *)malloc(sizeof(struct STACK_NODE));
    newNode->link = top;
    newNode->data = x;
    top = newNode;
}
 
int pop() {
    struct STACK_NODE *oldNode;
    int data;
 
    if (top == NULL) return -1;
 
    oldNode = top;
    data = top->data;
    top = top->link;
    free(oldNode);
 
    return data;
}
 
int size() {
    struct STACK_NODE *chaseNode;
    int count = 0;
 
    chaseNode = top;
 
    if (chaseNode == NULL) return count;
 
    while (chaseNode != NULL) {
        chaseNode = chaseNode->link;
        count++;
    }
    return count;
}
 
int empty() {
    if (top == NULL) return TRUE;
    else return FALSE;
}
 
int peek() {
    if (top == NULL) return -1;
    else return top->data;
}
 
int main() {
    int N;
    int userNum;
    char *stkState;
    int i = 1;
    int j = 0;
    int count = 0;
    int isSequence = TRUE;
 
    scanf("%d", &N);
    stkState = malloc(sizeof(char)*2*N);
 
    do {
        scanf("%d", &userNum);
        count++;
 
        while (peek() !=userNum) {
            if (peek() > userNum) {
                isSequence = FALSE;
                break;
            }
            push(i++);
            stkState[j++] = '+';
        }
        pop();
        stkState[j++] = '-';
        
    } while (count<N);
    
 
    if (isSequence == TRUE) {
        for (int i = 0; i < 2 * N;i++) {
            printf("%c\n",stkState[i]);
        }
    }
    else {
        printf("NO\n");
    }
 
    return 0;
}