백준알고리즘 1874번, 스택 수열

이번 문제에서는 스택을 클래스로 만들어 사용했다. 1~n까지의 수로 이루어진 수열을 스택을 이용해 재현해내는 문제이다. push를 할때는 1부터 순서대로 진행된다. 1~n까지 순서대로 push가 되기 때문에 수열을 재현해내기 불가능한 경우도 나온다. 만약 수열이 일부분이 5, 3 일 경우 5를 pop한 후에 바로 3을 pop하는 것은 불가능하다.(이전 단계에서 4를 pop해 놓지 않은 경우) 일반적으로 고려를 하자면 임의의 k를 pop한 경우 그 다음에 k를 넘어서는 값들이 올 경우 그만큼 push한 후에 pop을 하면 문제가 되지 않지만 k-1보다 작은 값들이 온다면 재현이 불가능한 경우가 된다. 아래 코드의 특이한 점은 변수를 이용해 1부터 n까지 순서대로 push한것이 아니라, 1~n까지의 값을 스택에 넣어 넣고 하나씩 pop하면서 사용했다. 스택 2개를 만들어 사용하는 것을 확인할 수 있을것이다.
전략: m을 pop해야 하는 경우 top이 m보다 작다면 m까지 push한후 pop. 크다면 불가능.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


#include <stdio.h>
#include <string.h>
#define MAX_STACK_SIZE 1000000

class Stack {
private:
 unsigned size;
 int stack[MAX_STACK_SIZE];
public:
 Stack() {
  size = 0;
  memset(stack, 0, sizeof stack);
 }
 int Size() {
  return size;
 }
 bool Empty(){
  return size == 0;
 }
 int Top(){
  if (size == 0)
   return 0;
  return stack[size-1];
 }
 void Push(int item)
 {
  stack[size++] = item;
 }
 int Pop() {
  return stack[--size];
 }

};


int main(void) {
 Stack st1, st2;
 int n;
 char sign[1000000] = { 0 };
 unsigned cnt = 0;
 int item;
#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
#endif
 scanf("%d", &n);
 for (int i = n; i > 0; i--)
 {
  st2.Push(i);
 }
 for (int i = 0; i < n; i++) {
  scanf("%d", &item);
  if (st1.Top() <= item)
  {
   while (st1.Top() < item)
   {
    st1.Push(st2.Pop());
    sign[cnt++] = '+';
   }
   st1.Pop();
   sign[cnt++] = '-';
  }
  else
  {
   printf("NO\n");
   return 0;
  }
 }
 
 #ifndef ONLINE_JUDGE
 fclose(stdin);
 fclose(stdout);
 #endif

 for (int i = 0; i < cnt; i++) {
  printf("%c\n", sign[i]);
 }

 return 0;
}

Contents