2751) 11. 정렬 : 수 정렬하기 2

문제

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

2751번: 수 정렬하기 2

 

풀이

• 백준 게시판에 올라온 풀이 Tip

   Quick Sort로 풀고 보나 마나 맞겠지 했다가 시간 초과가 떠서 당황했다. 시간 초과의 원인은,

최악의 경우(ex. 정렬 혹은 역정렬) $O(n^2)$의 시간 복잡도를 가지기 때문이었다.

 

 

Quick Sort

   아래 define으로 정의된 SWAP 함수를 매크로 함수라고 한다. 처음에 그냥 void swap(int* x, int* y) 꼴로 함수를 짜면 원본 값이 전해지지 않아 제대로 정렬이 이루어지지 않는다. 값이 복사되기 때문인데, 자세한 설명은 여기 참고.

#include "cstdio"

#define SWAP(x, y, temp) ( (temp) = (x), (x) = (y), (y) = (temp) )

int partition(int* data, int left, int right) {
    int low(left), high(right + 1), pivot(data[left]), temp(0);
    
    while(low < high) {
        do ++low; while(low <= high && data[low] < pivot);		// 왼쪽에서부터 pivot보다 값이 작을 동안 비교하며 올라감
        do --high; while(high >= left && data[high] > pivot);		// 오른쪽에서부터 pivot보다 값이 클 동안 비교하며 내려옴
        
        if(low < high) SWAP(data[low], data[high], temp);			// low와 high가 교차하지 않았으면 값 교환
    }
    
    SWAP(data[left], data[high], temp);						// 반복문을 빠져나온 건 low와 high가 교차했단 의미이므로 값 교환
    
    return high;		// pivot 위치를 반환
}

void qSort(int* data, int left, int right) {
    if(left < right) {
        int mid(partition(data, left, right));
        
        qSort(data, left, mid - 1);
        qSort(data, mid + 1, right);
    }
}

int main() {
    int repeat(0);
    
    scanf("%d", &repeat);
    int* data(new int[repeat]);
    
    for(int i(0); i < repeat; i++) scanf("%d", &data[i]);
    qSort(data, 0, repeat - 1);
    for(int i(0); i < repeat; i++) printf("%d\n", data[i]);
    
    delete[] data;
    return 0;
}

 

 

   그렇기 때문에 항상 $O(nlogn)$의 시간복잡도를 갖는 알고리즘 중 Merge Sort를 만들어보기로 했다(개념 및 코드는 여기 참고).

 

 

 

Merge Sort

#include "cstdio"

void merge(int* data, int left, int mid, int right) {
    int* result = new int[right + 1], i(left), j(mid + 1), cur(left);
    
    while(i <= mid && j <= right) {
    // 배열을 합병하면서 오름차순으로 정렬
        if(data[i] <= data[j]) result[cur++] = data[i++];
        else result[cur++] = data[j++];
    }
    
    /* original array에서(왼쪽 파티션을 다 helper에 카피했다면) 오른쪽 파티션의 끝나지 않은 부분은 이미 정렬되어 있는 상태이고,
    오른쪽 이기 때문에 helper array에 카피 후 다시 original array에 다시 카피 해 오는 작업은 불필요함 (cracking coding interview)*/
    while(i <= mid) result[cur++] = data[i++];
    // 남은 값들을 전부 정렬하는 배열로 옮김
    for(int idx(left); idx < cur; idx++) data[idx] = result[idx];
    // 정렬된 배열을 원본 배열로 옮김
    
    delete [] result;
}

void mSort(int* data, int left, int right) {
    if(left < right) {
        int mid((left + right) / 2);
        mSort(data, left, mid);
        mSort(data, mid + 1, right);
        merge(data, left, mid, right);
    }
}

int main() {
    int repeat(0);
    
    scanf("%d", &repeat);
    int* data = new int[repeat];
    
    for(int i(0); i < repeat; i++) scanf("%d", &data[i]);
    mSort(data, 0, repeat - 1);
    for(int i(0); i < repeat; i++) printf("%d\n", data[i]);
    
    delete[] data;
    return 0;
}

 

Merge/Quick Sort는 헷갈려서 몇 번 더 짜면서 복습해야겠다.

   

   직접 짜본답시고 삽질이 많았지만, 이 문제를 간단하게 푸는 방법은 역시 C++ STL을 이용하는 것이다.. 다 필요 없고 sort(data, data + repeat) 만 넣어주면 훨씬 빠르고 가볍게 작동한다.