[백준/C언어] 11650번 - 좌표 정렬하기

백준 웹사이트 "11650번 - 좌표 정렬하기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

11650번: 좌표 정렬하기

---

소스 코드

#include <stdio.h>

void merge_sort(int (*arr)[2], int index, int len);
void merge(int (*arr)[2], int l_index, int r_index, int l_len, int r_len);
int compare(int (*a)[2], int (*b)[2]);

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

    int coordinates[N][2];
    for(int i=0; i<N; i++){
        scanf("%d %d", &coordinates[i][0], &coordinates[i][1]);
    }
    
    //Merge Sort
    merge_sort(coordinates, 0, N);

    //출력
    for(int i=0; i<N; i++){
        printf("%d %d\n", coordinates[i][0], coordinates[i][1]);
    }
}

void merge_sort(int (*arr)[2], int index, int len){
    // Base Case
    if(len==1){
        return;
    }

    // Recursive Case
    // 1. arr을 반으로 나눈다
    int left = index;
    int right = index + len/2;
    int left_len = len/2;
    int right_len = len - len/2;

    // 2. 왼쪽, 오른쪽을 각각 merge_sort 한다
    merge_sort(arr, left, left_len);
    merge_sort(arr, right, right_len);

    // 3. 왼쪽, 오른쪽을 merge 한다
    merge(arr, left, right, left_len, right_len);
}

void merge(int (*arr)[2], int l_index, int r_index, int l_len, int r_len){
    //printf("merge: %d %d\n", l_index, r_index);
    // 1. 임시 배열 선언
    int temp[l_len+r_len][2];
    int count = 0;
    
    // 2. 왼쪽, 오른쪽의 가장 작은 수 비교
    int l_count = 0;
    int r_count = 0;
    while(1){
        int left = l_index + l_count;
        int right = r_index + r_count;
        if(compare(&arr[left], &arr[right])){ //arr[left] < arr[right]이면 1
            temp[count][0] = arr[left][0];
            temp[count][1] = arr[left][1];
            count++;
            l_count++;
        }
        else{
            temp[count][0] = arr[right][0];
            temp[count][1] = arr[right][1];
            count++;
            r_count++;
        }

    // 3. 왼쪽이나 오른쪽의 끝에 도달하면 break
        if(l_count==l_len || r_count==r_len){
            break;
        }
    }

    // 4. 남은 요소 temp로 복사
    if(l_count==l_len){ // 오른쪽을 복사
        while(count<l_len+r_len){
            temp[count][0] = arr[r_index+r_count][0];
            temp[count][1] = arr[r_index+r_count][1];
            count++;
            r_count++;
        }
    }
    else{               // 왼쪽을 복사
        while(count<l_len+r_len){
            temp[count][0] = arr[l_index+l_count][0];
            temp[count][1] = arr[l_index+l_count][1];
            count++;
            l_count++;
        }
    }

    // 5. arr에 임시배열 복사
    for(int i=l_index; i<l_index+l_len+r_len; i++){
        arr[i][0] = temp[i-l_index][0];
        arr[i][1] = temp[i-l_index][1];
    }
}

int compare(int (*a)[2], int (*b)[2]){  //a<b이면 1 반환
    if((*a)[0]<(*b)[0]){
        return 1;
    }
    else if((*a)[0]==(*b)[0]){
        if((*a)[1]<(*b)[1]){
            return 1;
        }
    }
    return 0;
}

---

문제 풀이

  좌표평면 위의 점들을 정렬하는 문제입니다. 쉬워보이는 문제이지만, x좌표와 y좌표를 같이 생각하기 위해 이차원 배열을 사용하여 조금 까다롭습니다. 특히, C언어의 경우 내장된 배열 함수가 없기에 포인터에 대한 개념을 확실히 이해한 후 코드를 짜는 것이 좋습니다. 포인터와 이차원 배열의 상관관계에 대한 내용의 Stack Overflow 링크를 남기겠습니다.

Pointer to 2D arrays in C

  이번 문제는 \(O(n^2)\)의 시간 복잡도를 가지는 정렬을 사용하면 시간 초과가 일어납니다 (직접 해봐서 확실합니다ㅠㅠ). 따라서 쉽게 짤 수 있는 거품 정렬 (Bubble Sort), 선택 정렬 (Selection Sort) 등은 사용할 수가 없죠. \(O(nlogn)\)의 시간 복잡도를 가지는 정렬 중에서 저는 병합 정렬 (Merge Sort)를 이용해 문제를 풉니다. 조금 더 쉽게 풀기 위해, 2751번에서 사용한 Merge Sort 코드를 가져와 문제에 맞게 수정해줍니다.

  핵심은 함수 내부에서 배열 arr을 이용하기 위해 파라미터로 int * arr을 사용하는 대신, int (*arr)[2]를 사용하는 것입니다. 이렇게 하면, arr을 일차원 배열로 접근하지 않고, 이차원 배열로 접근하게 됩니다. 또한, 2751번에서 arr[left]와 arr[right]를 비교할 때 단순히 arr[left]<arr[right]을 통해 비교할 수 있었는데, 이차원 배열이 되며 수정할 필요가 생깁니다. 따라서 이차원 배열의 비교를 위한 새로운 함수 'compare'을 선언합니다. 두 변수 int (*a)[2]와 int (*b)[2]를 받는데, 두 변수 모두 크기 2의 int 배열을 가리키는 포인터입니다. 차례로 x좌표에 해당하는 (*a)[0]과 (*b)[0]을 비교하고, y좌표에 해당하는 (*a)[1]과 (*b)[1]을 비교하여 a, b의 대소관계를 파악하고, 그 결과를 반환합니다. 이때 a가 b보다 작으면 1을 반환하고, 더 크면 0을 반환하도록 합니다. 여기서 포인터에 관한 개념이 확실히 잡혀있지 않다면 굉장히 헷갈릴 것입니다. 확실히 이해한 후 코딩해줍시다!

  위에 설명한 부분들 외에도 여러 수정 사항들이 있습니다. 그러나 전체적인 알고리즘은 동일하며, 수정 사항들은 모두 일차원 배열에서 이차원 배열로 변경하기 위한 과정임을 파악하면 이해하기 쉬울 것입니다.

  아래는 백준 웹사이트 "2751번 - 수 정렬하기 2" 문제풀이 링크입니다. 2751번에는 병합 정렬 (Merge Sort)에 관한 설명이 나옵니다.

[백준/C언어] 2751번 - 수 정렬하기 2