[C언어 백준 풀이] 11651번 : 좌표 정렬하기 2 (C로 메모리 초과 없이 푸는 법)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 11651번 문제인 '좌표 정렬하기 2'를 C++이 아닌 C언어로 풀이하는 방법을 다루고 있습니다.

 

 

쉬운 문제들을 풀다가 맞게 풀었는데 메모리 초과가 뜨는 문제가 있어 이를 어떻게 해결했는지 작성하고자 합니다.

간단한 정렬 문제로 C++의 algorithm.h를 사용한다면 쉽게 정렬이 가능하지만, 해당 헤더 파일을 지원하지 않는 C언어에서는 메모리 초과 없이 어떻게 푸는지를 정리했습니다.

 

 

11651번 : 좌표 정렬하기 2

 

문제만 읽어보면 간단한 좌표 정렬 문제입니다.

y좌표를 우선으로 오름차순으로 정렬하고, y좌표가 같을 경우 x좌표가 낮은 것을 먼저 정렬해서 출력하는 문제입니다.

N이 100000 이하이기 때문에, O(N^2)의 정렬 알고리즘을 사용하면 시간 초과가 발생할 것으로 보입니다.

따라서 O(N log N) 정렬 알고리즘인 병합 정렬(merge sort) 또는 퀵 정렬(quick sort)을 사용해야 합니다.

 

#include<stdio.h>

int merge(int x[], int y[], int left, int mid, int right) {
    int xCopy[100005], yCopy[100005];
    int i = left, j = mid+1, k = left;
    while(i<=mid && j<=right) {
        if(y[i]<y[j] || (y[i]==y[j] && x[i]<x[j])) xCopy[k] = x[i], yCopy[k++] = y[i++];
        else xCopy[k] = x[j], yCopy[k++] = y[j++];
    }
    while(i<=mid) xCopy[k] = x[i], yCopy[k++] = y[i++];
    while(j<=right) xCopy[k] = x[j], yCopy[k++] = y[j++];
    for(int a=left; a<=right; a++) x[a] = xCopy[a], y[a] = yCopy[a];
}

int mergeSort(int x[], int y[], int left, int right) {
    int mid;
    if(left < right) {
        mid = (left + right)/2;
        mergeSort(x, y, left, mid);
        mergeSort(x, y, mid+1, right);
        merge(x, y, left, mid, right);
    }
}

int main() {
    int n, x[100005], y[100005];
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d %d", &x[i], &y[i]);
    mergeSort(x, y, 0, n-1);
    for(int i=0; i<n; i++) printf("%d %d\n", x[i], y[i]);
}

 

초기에는 위와 같이 (접은 글) Merge Sort를 사용하여 해결하려고 했습니다. (동률일 때 순서가 바뀌지 않기 때문에 안정한 정렬 방법이므로 일반적으로 사용해왔음)

그러나 메모리 초과가 발생했는데, 그것은 10만 크기의 배열을 4개나 선언했기 때문으로 보입니다.

따라서 메모리를 더 적게 사용하면서 해결할 수 있는 방법을 찾아야 했습니다.

 

#include<stdio.h>

void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

int partition(int x[], int y[], int left, int right) {
    int pivot = y[left], pivot_adr = left, low = left+1, high = right, temp;
    while(low <= high) {
        while(low <= right && (pivot > y[low] || (pivot == y[low] && x[pivot_adr] > x[low]))) low++;
        while(high >= (left+1) && (pivot < y[high] || (pivot == y[high] && x[pivot_adr] < x[high]))) high--;
        if(low <= high) swap(x, low, high), swap(y, low, high);
    }
    swap(x, left, high);
    swap(y, left, high);
    return high;
}

void quickSort(int x[], int y[], int left, int right) {
    if(left <= right) {
        int pivot = partition(x, y, left, right);
        quickSort(x, y, left, pivot-1);
        quickSort(x, y, pivot+1, right);
    }
}

int main() {
    int x[100005], y[100005], n;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d %d", &x[i], &y[i]);
    quickSort(x, y, 0, n-1);
    for(int i=0; i<n; i++) printf("%d %d\n", x[i], y[i]);
}

 

따라서 배열을 옮기지 않고 바꿔야 하는 원소들을 발견하는 즉시 그 자리에서 swap하는 Quick Sort를 사용했습니다.

퀵 정렬을 사용하면 배열을 약 20만의 크기(x 좌표와 y 좌표 2개)로 선언하면서 구현이 가능했습니다.

까다로울 수 있는 부분은 조건문인데, 이것은 y좌표가 우선 순위가 높으므로 pivot으로 잡아주고, 대신 pivot의 주소를 저장해두었다가 y좌표가 동률일 때 pivot의 주소를 가지고 x좌표에서 비교해서 swap을 수행할지 말지를 결정해주면 됩니다.

설명으로는 조건 이해가 어려우신 분들은 위 코드의 12행과 13행의 조건문을 참고하여 이해하시면 됩니다.