11월 3주차 Ec.crew (스택)

백준 1874번 : 스택 수열

1874번: 스택 수열 (acmicpc.net)

1874번: 스택 수열

#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100000

int stack[STACK_SIZE];
int top=-1;

//스택 공백 상태
int IsEmpty(){
    if(top==-1)
        return 1;
    else
        return 0;
}

//삽입 함수
void push(int value){
    stack[++top]=value; //top을 1 증가시키고 value값을 스택에 push
}

//삭제 함수
int pop(){
    if(IsEmpty()==1)
        return 'f'; //스택 공백 상태면 'f'를 출력
    else
        return stack[top--]; //스택이 공백상태가 아니라면 맨 위의 원소 하나를 pop
}

int main(){
    int N,target,res;

    scanf("%d",&N); //N은 첫 줄에 입력받는 정수값

    //동적 메모리 할당으로 char 배열 생성
    char* result = (char*)malloc(sizeof(char)*(N*2 +1));

    //오름차순 arr에 들어있는 수라고 가정.
    int j=1;
    int k=0;

    for(int i=0;i<N;i++){
        scanf("%d",&target);
        while(j <= target){ //j는 오름차순으로 스택에 넣을 1,2,...
            push(j);
            // printf("+\n");
            result[k++] = '+'; //result 배열의 k번째 원소에 '+'넣기
            j++; //j값 증가
        }
        res = pop(); // 스택의 가장 위에 있는 원소를 삭제. 그 원소를 res에 넣음
        if(res == target){ // pop한 값인 res가 target과 같으면
            // printf("-\n");
            result[k++] = '-'; //result 배열의 K번째 원소에 '-' 넣기
        }
        else{
            // printf("NO\n");
            printf("NO\n");
            free(result);
            return 0;
        }
    }
    for(int i=0;i<N*2;i++){
        printf("%c\n",result[i]); //result 배열의 값 모두 출력
    }

    return 0;
}