📝 Baekjoon 1874 문제풀이

---

💡문제 정의

문제는 위와 같다. 처음에 문제를 읽고 이게 무슨 말...? 하다가 힌트를 읽고 문제의 의미를 이해했다.

n과 특정 수열이 주어질때, 1부터 n까지의 숫자를 스택에 push & pop 하면서 이 특정 수열을 만들 수 있는지 판별해야 한다. 단, 스택에 숫자를 push 할 때는 1~n까지 차례대로! 오름차순으로만! push 가능하다. 만약 주어진 수열을 만들 수 있다면 push와 pop 연산을 어떤 순서로 수행하면 되는지 출력한다(push 연산은 '+', pop 연산은 '-'로 출력).

소스코드는 아래와 같다.

1) C

# include <stdio.h>

int arr[100000] = {0, };
char ans[200000];

typedef struct stack_ {
  int items[100000];
  size_t top;
} stack;

void s_init(stack *s) {
  s->top = 0;
}

int is_empty_stack(stack *s) {
  return s->top == 0;
}

void s_push(stack *s, int item) {
  s->items[s->top++] = item;
}

int s_pop(stack *s) {
  if (is_empty_stack(s)) return -1;
  else {
    int res = s->items[s->top - 1];
    s->top--;
    return res;
  }
}

int main(void) {
  int n;
  scanf("%d", &n);

  stack s;
  s_init(&s);

  for (int i = 0;i < n;i++) {
    scanf("%d", &arr[i]);
  }

  int index = 0, index2 = 0;
  int num = 1;

  s_push(&s, num);
  ans[index2++] = '+';
  while (1) {
    int target = arr[index];
    int top;
    if (is_empty_stack(&s)) top = -1;
    else top = s.items[s.top - 1];

    if (target == top) {
      ans[index2++] = '-';
      s_pop(&s);
      index++;
    }
    else {
      ans[index2++] = '+';
      s_push(&s, ++num);
    }

    if (index == n) {
      for (int j = 0;j < index2;j++) printf("%c\n", ans[j]);
      break;
    }
    else if (num > n) {
      printf("NO\n");
      break;
    }
  }

  return 0;
}

• arr: 주어지는 수열을 저장할 배열
• ans: push, pop 연산('+' / '-')을 저장할 배열
• index: 주어지는 수열의 target을 가리키는 인덱스(arr 배열의 인덱스). target과 스택의 top이 같을 경우에만 증가.
• index2: ans 배열의 인덱스

index는 target과 스택의 top이 같을 경우에만 증가하므로, loop의 마지막 부분에서 index가 n과 같다면 push, pop을 통해 수열을 만들기에 성공했다는 의미. 따라서 ans 배열에 저장된 push, pop 연산을 출력하고 break.

만약 num이 n보다 크다면, 1부터 n까지의 숫자를 스택에 push, pop 하면서 수열을 만들지 못 했다는 의미이므로 NO를 출력하고 break.