문제

풀이

stack 자료구조를 이용하여 push(), pop() 두 함수로 구현하였다. 기본적인 함수와 자료구조는 9012번에서 사용했던 함수 그대로 가져와서 사용하였고, input 조건에 따라 MAX_STACK_SIZE만 100000으로 변경해 주었다.

1부터 input N까지 ascending order로 있는 arr가 있다고 가정하고,
input을 받음과 동시에 그 수를 target이라고 할 때,
target까지 ascending order arr가 도착할 때까지 push()를 반복하며,
pop()을 수행하였을 때 target과 pop()의 return값이 다르면 fail을 하도록 하였다.

수도코드는 대충 다음과 같다.

while(target까지 도착)
	push();
if(pop() == target) print('-');
else fail

검색한 것

없음.

코드

코드를 보면 주석으로 printf가 있는데, 'NO'를 출력하기 전에 쓸데없는 '+', '-'같은 애들이 출력되기 때문에 이를 막고 result를 저장하는 배열을 추가로 만들어서 구현해야 했다.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_STACK_SIZE 100000

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

int IsEmpty(){
  if(top<0)
    return 1;
  else
    return 0;
}

void push(int value){
  stack[++top]=value;
}
 
int pop(){
  if(IsEmpty()==1)
    return 'f';
  else 
    return stack[top--];
}

int main(){
  int N, i, target,j,res,k;
  char* result;

  scanf("%d",&N);
  // result array
  result = (char*)malloc(sizeof(char)*(N*2 +1));

  // ascending order arr에 들어있는 수라고 가정.
  j=1;
  k=0;

  for(i=0;i<N;i++){
    scanf("%d",&target);
    while(j <= target){
      push(j);
      // printf("+\n");
      result[k++] = '+';
      j++;
    }
    res = pop();
    if(res == target){
      // printf("-\n");
      result[k++] = '-';
    }else{
      // printf("NO\n");
      printf("NO\n");
      free(result);
      return 0;
    }
  }
  for(i=0;i<N*2;i++){
    printf("%c\n",result[i]);
  }

  return 0;
}