알고리즘 > 자료구조A > 불쾌한날(1141)

Question

http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=1141

Solving

스택에 들어올 다음 수와 top과 비교한다.

1) top이 더 크다면 그냥 push, 

2) top이 작다면 pop하고, 

3) 다음 top과 다시 비교하여, top이 크다면 1) 로, 작다면 2) 로 간다.

주어진 테스트 케이스로 그려보면 아래와 같이 진행된다.

           2

           2       4       4                1

 5        5       5       5       6       6

[0]    [1]    [2]    [3]    [4]    [5]

 4       1       2       1       2       1

 3       0       1       0       1       0

위 표에서 4 1 2 1 2 1은 각 단계에서 push된 값이 몇 단계나 살아 남는지 적은 것이다.

5의 경우 0단계에서 push되어 3단계까지 살아남고 4단계에서 pop이 된다.

4 1 2 1 2 1 에 -1을 하면 3 0 1 0 1 0이 나오게 되고, 이것의 합이 우리가 구하고자하는 답이 된다.

Code

Colored By Color Scripter™

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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

#include <stdio.h> #pragma warning(disable:4996)   int n; long long int sum;   typedef struct _node {     int val;     int idx; }node;   node arr[80005]; node tmp1;   // stack용 int cnt_stack, bottom_stack; node stack[80005];   // void algo(node tmp, int idx); int empty(); node top(); void push(node num); node pop();   int main() {     FILE *fin = fopen("input.txt", "rt");     FILE *fout = fopen("output.txt", "wt");       //scanf("%d", &n);     fscanf(fin, "%d", &n);     for (int i = 1; i <= n; i++)     {         //scanf("%d", &arr[i].val);         fscanf(fin, "%d", &arr[i].val);         arr[i].idx = i;     }       for (int i = 1; i <= n; i++)     {         algo(arr[i], i);           if (i == n)         {             for (int j = cnt_stack; j > 0; j--)             {                 if (!cnt_stack)                     break;                 tmp1 = pop();                 stack[cnt_stack + 1].idx = 0;                 stack[cnt_stack + 1].val = 0;                 sum += (i - tmp1.idx);             }         }     }       fprintf(fout, "%lld\n", sum);     //printf("%lld\n", sum); }   void algo(node tmp, int idx) {     if (empty())     {         push(tmp);         return;     }       for (int i = cnt_stack; i >= 0; i--)     {         if (empty())         {             push(tmp);             return;         }         if (top().val <= tmp.val)         {             tmp1 = pop();             stack[cnt_stack + 1].idx = 0;             stack[cnt_stack + 1].val = 0;             sum += (idx - tmp1.idx) - 1;         }         else         {             push(tmp);             break;         }     }   }   int empty() {     if (!cnt_stack)         return 1;     return 0; }   node top() {     return stack[cnt_stack]; }   void push(node num) {     if (cnt_stack == n)         return;     cnt_stack++;     stack[cnt_stack] = num; }   node pop() {     if (!cnt_stack) // empty     {         node temp = { 0, 0 };         return temp;     }     cnt_stack--;     return stack[cnt_stack + 1]; }