[13415번] 정렬 게임

문제 출처 :

https://www.acmicpc.net/problem/13415

알고리즘 분석 :

문제 해결에 필요한 사항

1. deque

2. sort

3. 문제에 대한 이해

http://hae.so/kmupc.pptx :: 국민대학교 교내 프로그래밍 경진대회 문제풀이 슬라이드

위의 링크에서 정렬 게임의 알고리즘을 통해 해결하였다.

다른점이라고 하면, ppt에서의 알고리즘 해석은 두 pos를 두고 오름차순, 내림차순에 대해 값을 넣어주지만,

아래 코드에서는 deque를 통해 뒤로 넣어주고 마지막 정렬해야하는 값들에 대해서는 앞으로 빼며

정렬을 해주는 방식의 차이가 있다.

소스 코드 : 

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

#include <iostream> #include <algorithm> #include <deque> #include <cstdio>   using namespace std;   bool comp(const int &a, const int &b) {     return a > b; } int arr[100001];   int main() {     deque<int> order;     deque<int> value;     int n;       scanf("%d", &n);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       int tc; // test case     int flag = 0;     int up, down;       scanf("%d", &tc);       // 정렬 횟수만큼     for (int i = 0; i < tc; i++)     {         // 오름차순, 내림차순 입력받는다.         scanf("%d %d", &up, &down);           int tmp;           tmp = up;           // 데크에 값이 비어있지 않다면         while (!value.empty())         {             // 값이 비어있지 않고 만약 데크의 값이 tmp값보다 작거나 같다면             if (!value.empty() && value.back() <= tmp)             {                 // pop을 한다.                 value.pop_back();                 order.pop_back();             }               // 값이 비어있거나, 데크의 값이 tmp값보다 크다면             else             {                 // push를 한다.                 value.push_back(tmp);                 order.push_back(flag);                 break;             }         }           // 만약 위의 과정에서 if문에 의해 pop만 되고 탈출하면         // 값이 없으므로 tmp의 값을 넣어준다.         if (value.empty())         {             value.push_back(tmp);             order.push_back(flag);         }           // 위의 주석과 동일         tmp = down;           while (!value.empty())         {               if (!value.empty() && value.back() <= tmp)             {                 value.pop_back();                 order.pop_back();             }               else             {                 value.push_back(tmp);                 order.push_back(!flag);                 break;             }         }           if (value.empty())         {             value.push_back(tmp);             order.push_back(!flag);         }     }         // sort는 0~val만큼 하면되고, ord가 0이면 오름차순, 1이면 내림차순으로 하면된다.     while (!value.empty())     {         int val = value.front();         int ord = order.front();           value.pop_front();         order.pop_front();           // ord == 1 :: 내림차순, ord == 0 :: 오름차순,         ord ? sort(arr, arr + val, comp) : sort(arr, arr + val);     }       // 출력     for (int i = 0; i < n; i++)         printf("%d ", arr[i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus