[BOJ-13415]정렬게임

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

[문제요약]

주어진 N개의 수를 정렬을 한다. 

K번 세트로 정렬을 하며, [1,K] 세트에서 각 세트로 주어지는 A D 는 A는 주어진 수 중 [0,A-1] 까지 오름차순 정렬, D는 주어진 수 중 [0,D-1] 까지 내림차순 정렬을 한다.

[문제풀이]

우선 K개 세트를 모두 입력을 받는다. 

이때 0,1,....,x,....,y,...,z,...K, K-1 세트가 있다고 할 때

오름차순과 내림차순 세트를 구분시켰다. 

그래서 

0,1,.....,2*(K-1),2*(K-1)+1 로 나눌 수 있다. 

번호를 붙여서 sort를 하게 되는데 [0,range) 가 크며, 같은 경우에는 no번호가 크면 앞으로 오게 한다. 

가장 큰 range를 가진 경우에는 이전에 정렬시키는 것은 의미가 없기 때문이다. 

이러한 이유는 

1 2 3 4 5 .... N 까지 수가 나열되어 있는 경우. (물론 수는 정렬되어 주어지지 않는다고 가정한다.)

i번째 세트에서 오름차순으로 정렬되어 있는데 [0,p) 까지 정렬을 시켜야 한다고 하자.

이전 세트에서는 p보다 큰 경우가 없을 때 [0,p) 를 정렬시키면, 이전세트에서 정렬시키는 것은 하지 않아도 되므로 정렬을 시킨 이유이다.

이제 제일 큰 정렬 범위를 찾았다면, 현재 진행 중인 finish_set 을 갱신시킨다. finish_set 보다 작은 경우가 나오면 그 경우는 처리하지 않아도 된다.

그렇기 때문에 정렬하는 횟수를 줄일 수 있다. 

위 풀이코드로 120ms, 다른 분들은 dequeue 로 풀이를 하였고 60ms, 속도차이가 60ms 정도 나는 것 같다.

[C++ source code]

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include<vector>
#define din1(a) scanf("%d",&a)
using namespace std;
vector<int> input;
 
bool descending(int a, int b) {
    return a > b;
}
struct info {
    int no;
    int range;
    info() {}
    info(int ino, int irange) : no(ino), range(irange) {}
};
 
bool cmp_info(info a, info b) {
    if (a.range > b.range) return true;
    else if (a.range == b.range) return a.no > b.no;
    return false;
}
int main() {
    int n, k;
    din1(n);
    int temp;
    for(int i = 0 ; i < n ; i++){
        din1(temp);
        input.push_back(temp);
    }
    din1(k);
 
    vector<info> v;
    for(int i = 0 ; i < k ; i++){
        int a, b;
        din1(a);
        din1(b);
        v.push_back(info(2 * i + 0, a));
        v.push_back(info(2 * i + 1, b));
    }
    sort(v.begin(), v.end(), cmp_info);
 
    int finish_set = -1;
    for (int i = 0; i < v.size(); i++) {
        info here = v[i];
        int hno = here.no;
        int hrange = here.range;
 
        if (finish_set < hno) finish_set = hno;
        else continue;
 
        if (hno & 1) sort(input.begin(), input.begin() + hrange, descending);
        else if (!(hno & 1)) sort(input.begin(), input.begin() + hrange);
    }
 
    for (auto it : input) printf("%d ", it);
 
    puts("");
    return 0;
}