알고리즘 문제해결 전략

Ch.29.2 문제 ID SORTGAME

종만북

29.2 문제: Sorting Game ( 문제ID : SORTGAME, 난이도: 중)

[algo] : https://www.algospot.com/judge/problem/read/SORTGAME

시사점
- map은 Hash와 비슷한 방법이므로 접근하는 속도가 중요합니다.
- smaller변수를 이용해 arr[i]가 arr 원소들 중 몇번째로 큰 숫자인지 표현해내는 방법이 신박합니다.

문제 이해

입력으로 주어진 길이 n인 배열이 있습니다.
해당 배열을 뒤집기만 사용하여 정렬을 해야 한다고 할때, 최소 뒤집기 횟수를 구하여야 합니다.

그래프로 바꾸기

문제에 주어진 최초 배열을 시작 상태로 생각하여 그래프로 변환할 수 있습니다.
즉, 길이 n인 배열이 주어졌을때,
- start = 0, end = 2부터 시작하여 해당 상태에 대해 모든 경우를 뒤집어 볼 수 있습니다.
- end가 2부터 시작하는 이유는 reverse특성상 end포인트는 뒤집지 않는 지점을 의미하기 때문입니다.
n개의 원소에 대해 이들을 배열하는 방법은 n!가지입니다.
예를 들어, {3,4,1,2}를 뒤집어 본다면 아래와 같이 6가지의 경우가 나옵니다.
- {4,3,1,2}, {1,4,3,2}, {2,1,4,3}, {3,1,4,2}, {3,2,1,4}, {3,4,2,1}
해당 방법을 사용하여 naive하게 구현하면 아래와 같은 코드를 가지고, 시간초과를 유발합니다.

int bfs(const vector<int>& perm){
    int n = perm.size();
    // 목표 정점을 미리 계산한다.
    vector<int> sorted = perm;
    sort(sorted.begin(), sorted.end());
    // 방문 목록(큐)과 시작점부터 각 정점까지의 거리
    queue<vector<int> > q;
    map<vector<int>,int> distance;
    // 시작점을 큐에 넣는다.
    distance[perm] = 0;
    q.push(perm);
    while(!q.empty()){
        vector<int> here = q.front(); q.pop();
        // 목표 정점을 발견했으면 곧장 종료한다.
        if(here == sorted) return distance[here];
        int cost = distance[here];
        // 가능한 모든 부분 구간을 뒤집어 본다.
        for(int i = 0; i < n; ++i){
            for(int j = i + 2; j <= n; j++){
                reverse(here.begin()+i, here.begin() + j);
                if(distance.count(here) == 0){
                    distance[here] = cost + 1;
                    q.push(here);
                }
                reverse(here.begin()+i, here.begin() + j);
            }
        }
    }
    return -1;
}

너무 느리다

이때 저자가 제시하는 방법은 전처리 과정을 수행하는 것입니다.
해당 부분을 미리 진행하면 몇 십배 빨라지고, 이는 문제에서 요구하는 제한시간 내에 통과를 일으킵니다.
확실히, 전처리할 수 있는 내용은 전처리 하는게 조금이라도 빨라진다는 시사점을 가지고 있으므로, 기억하는 게 좋다고 생각합니다.
근본적으로, map에 접근하는 데 드는 시간이 크기 때문에 시간초과가 발생합니다.
아래와 같은 두 가지 사실을 통해, 문제를 최적화할 수 있습니다.

1. 숫자들이 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같습니다. 예를 들어 두 배열
   {30,40,10,20}과 {3,4,1,2}는 숫자들의 상대적 크기가 같기 때문에 필요한 최소 연산 수도 2로
   같습니다.
2. 이 문제의 상태 공간은 양방향 그래프이기 때문에, 시작 정점에서 목표 정점으로 가는 최단 거리는 목표
   정점에서 시작 정점으로 가는 최단 거리와 같습니다. 다시 말해 한 배열을 정렬하는 데 드는 연산의
   수는 정렬된 배열을 원래 배열로 바꾸는 데 드는 연산의 수와 같다는 말입니다.

아래 코드에서 이해가 되지 않았던 변수는 smaller입니다.
- 찾아보고 이해한 결과, 전체 길이 n인 순열 중 i번째 인자가 상대적으로 몇번째 순서에 해당하는지 나타내줍니다.
- 왜냐하면, 우리는 precalc를 통해서 0부터 n-1까지만 상대적으로 map에 저장해두었기 때문입니다.

map<vector<int>, int> toSort;
// [0, .. , n-1]의 모든 순열에 대해 tosort[] 를 계산해 저장한다.
void precalc(int n){
    vector<int> perm(n);
    for(int i = 0; i < n; i++)perm[i] = i;
    queue<vector<int> > q;
    q.push(perm);
    toSort[perm] = 0;
    while(!q.empty()){
        vector<int> here = q.front(); q.pop();
        int cost = toSort[here];
        for(int i = 0; i < n; ++i){
            for(int j = i + 2; j <= n; ++j){
                reverse(here.begin() + i, here.begin() + j);
                if(toSort.count(here) == 0){
                    toSort[here] = cost+1;
                    q.push(here);
                }
                reverse(here.begin() + i, here.begin() + j);
            }
        }
    }
}
int solve(const vector<int>& perm){
    // perm을 [0, .. n-1]의 순열로 변환한다.
    int n = perm.size();
    vector<int> fixed(n);
    for(int i = 0; i < n; i++){
        int smaller = 0;
        for(int j = 0; j < n; j++){
            if(perm[j] < perm[i])
                ++smaller;
        }
        fixed[i] = smaller;
    }
    return toSort[fixed];
}