[백준] 11650번: 좌표 정렬하기 - C++

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 x_i와 y_i가 주어진다. (-100,000 ≤ x_i, y_i ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

 

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

---

정렬을 이용하여 푸는 문제.

병합 정렬을 사용하여 풀었고, x좌표가 증가하는 순으로 - x좌표가 같으면 y좌표가 증가하는 순으로 정렬해야되기 때문에 조건문을 하나 더 붙였다.

 

코드

#include <cstdio>

void merge(int** sorted, int** arr, int begin, int mid, int end);
void mergeSort(int** sorted, int** arr, int begin, int end);
void printArr(int** arr, int n);

int main(void) {
    int n;
    scanf("%d", &n);

    int** arr = new int*[n];
    for(int i = 0; i < n; i++) {
        arr[i] = new int[2];
    }
    int** sorted = new int*[n];
    for(int i = 0; i < n; i++) {
        sorted[i] = new int[2];
    }

    for(int i = 0; i < n; i++) {
        scanf("%d %d", &arr[i][0], &arr[i][1]);
    }

    mergeSort(sorted, arr, 0, n - 1);
    printArr(arr, n);

    for(int i = 0; i < n; i++) {
        delete[] arr[i];
        delete[] sorted[i];
    }
    delete[] arr;
    delete[] sorted;
    return 0;
}

void merge(int** sorted, int** arr, int begin, int mid, int end) {
    int i, j, k;
    i = begin;
    j = mid + 1;
    k = begin;

    while(i <= mid && j <= end) {
        if(arr[i][0] < arr[j][0]) {
            sorted[k][0] = arr[i][0];
            sorted[k][1] = arr[i][1];
            i++;
        }
        else if(arr[i][0] == arr[j][0]) {
            if(arr[i][1] < arr[j][1]) {
                sorted[k][0] = arr[i][0];
                sorted[k][1] = arr[i][1];
                i++;
            }
            else {
                sorted[k][0] = arr[j][0];
                sorted[k][1] = arr[j][1];
                j++;
            }
        }
        else {
            sorted[k][0] = arr[j][0];
            sorted[k][1] = arr[j][1];
            j++;
        }
        k++;
    }
    if(i > mid) {
        for(int a = j; a <= end; a++, k++) {
            sorted[k][0] = arr[a][0];
            sorted[k][1] = arr[a][1];
        }
    }
    else {
        for(int a = i; a <= mid; a++, k++) {
            sorted[k][0] = arr[a][0];
            sorted[k][1] = arr[a][1];
        }
    }

    for(int a = begin; a <= end; a++) {
        arr[a][0] = sorted[a][0];
        arr[a][1] = sorted[a][1];
    }
}

void mergeSort(int** sorted, int** arr, int begin, int end) {
    int mid;
    if(begin < end) {
        mid = (begin + end) / 2;
        mergeSort(sorted, arr, begin, mid);
        mergeSort(sorted, arr, mid + 1, end);
        merge(sorted, arr, begin, mid, end);
    }
}

void printArr(int** arr, int n) {
    for(int i = 0; i < n; i++) {
        printf("%d %d\n", arr[i][0], arr[i][1]);
    }
}