[그리디 문제풀기] Google Code Jam 2018 - Qualification Round (문제 B) (C/C++)

문제 B: 트리플 버블 정렬(Trouble Sort)

Code Jam - Google’s Coding Competitions

 

 

간략한 문제 해석

원래 버블 정렬 알고리즘은 앞뒤의 두 원소를 비교해 크기가 더 작은 것이 앞으로 오도록 순서를 정렬하는 것이다.

이 문제에서는 인접한 두 원소가 아니라, 가운데에 어떤 원소를 기준으로 양옆의 원소를 비교해 크기가 작은 것이 앞으로 오도록 정렬하는 '트러블(Triple + Bubble) 알고리즘'을 사용한다. 이 방법을 사용했을 때 주어진 배열을 정상적으로 정렬할 수 있다면 'OK'를, 없다면 처음으로 정렬이 아니게 되는 인덱스가 몇인지를 출력한다.

예시로 5 6 8 4 3은 다음과 같이 정렬을 수행한다.

5 6 8 4 3
5 4 8 6 3
5 4 3 6 8
3 4 5 6 8

=> 정상적으로 정렬됐다.

하지만 8 9 7을 돌리면 다음과 같이 된다.

8 9 7
7 9 8

이 경우 정렬을 다 수행했음에도 불구하고 크기에 맞게 정렬되지 않았기 때문에 정상적으로 정렬할 수 없다.

 

틀린 풀이

문제에서 주어진 트리플 버블 정렬 코드를 넣고 정렬된 배열인 v를 차례로 돌면서 검사하면 Test Set 2에서 시간초과가 발생한다.

#include <string>
#include <vector>

using namespace std;

int main() {
    int t, n, tmp, i=0;
    vector<int> v;
    scanf("%d", &t);
    for(int j=1; j<=t; j++) {
        scanf("%d", &n);
        v.clear();
        for(i=0; i<n; i++) {
            scanf("%d", &tmp);
            v.push_back(tmp);
        }
        // 트러블 정렬
        bool done = false;
        while(!done) {
            done = true;
            for(i=0; i<v.size()-2; i++) {
                if (v[i] > v[i+2]) {
                    done = false;
                    tmp = v[i];
                    v[i] = v[i+2];
                    v[i+2] = tmp;
                }
            }
        }
        // 정상적인 정렬인지
        for(i=0; i<v.size()-1; i++) {
            if(v[i] > v[i+1]) {
                done = false;
                break;
            }
        }
        if(done) printf("Case #%d: OK\n", j);
        else printf("Case #%d: %d\n", j, i);
    }

    return 0;
}

 

Test set 2 에서 시간초과

 

핵심 알고리즘

이 문제를 해결하기 위해서는 홀수와 짝수를 구분해 처리하면 된다. 홀수와 짝수는 서로 정렬에 관여할 수 없다는 점이 핵심이다.
홀수는 홀수끼리, 짝수는 짝수끼리 정렬해서 최종적으로 문자열이 오름차순 정렬을 이루고 있는지 확인하면 된다.

시간복잡도 O(N^2)의 버블 정렬이 아닌 C++ STL에서 제공하는 힙구조에 가까운 정렬을 각각 한번씩 해주면 되기 때문에 훨씬 빨라진다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> odd;
vector<int> even;

int main() {
    int t, n, tmp;
    scanf("%d", &t);
    for(int i=1; i<=t; i++) {
        odd.clear();
        even.clear();
        printf("Case #%d: ", i);
        scanf("%d", &n);
        for(int j=0; j<n; j++) {
            scanf("%d", &tmp);
            if(j%2 == 0) {
                odd.push_back(tmp);
            } else {
                even.push_back(tmp);
            }
        }
        sort(odd.begin(), odd.end());
        sort(even.begin(), even.end());
        int now = 0;
        bool sorted = true;
        for(int j=0; j<n; j++) {
            if(j%2 == 0) {  // 홀수번째일 때
                if(odd[j/2] < now) {    // 앞에 있는 수가 더 크면 now의 인덱스 뱉기
                    printf("%d\n", j-1);
                    sorted = false;
                    break;
                } else {    // 뒤에 있는 수가 더 크면 다음 배열 보러 넘어감
                    now = odd[j/2];
                }
            } else {    // 짝수번째일 때
                if(even[j/2] < now) {
                    printf("%d\n", j-1);
                    sorted = false;
                    break;
                } else {
                    now = even[j/2];
                }
            }
        }
        if(sorted) printf("OK\n");
    }

    return 0;
}

 

Test set 둘 다 통과

 

참고글

37. 구글 코드 잼(Google Code Jam) 2018에서 살펴보는 기초 그리디 문제