[C] 백준 11650번: merge sort 복습

📎 백준 11650번 풀러 가기

11650번: 좌표 정렬하기

문제

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

입력

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

출력

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

---

호호 그동안 밀린 강의랑 과제를 해서 문제를 못 풀다가,

오늘 좀 여유로워져서 한 문제 풀었다!

 

오래 걸리거나 생각해야 하는 문제는 아니었고,

지난번에 구현해보았던 mergesort를 다시 구현해보는 식으로 했다.

 

지난번이 처음이었고, 이번이 두 번째라 약간 헤매기는 했지만머릿속으로 merge sort의 작동방식을 잘 떠올리면서 해보니 잘 되었다!

 

조금만 더 익숙해지면, 알고리즘 시간에 코딩테스트를 볼 때도 덜 고생할 수 있을 것 같다😄

---

아래는 내가 구현한 코드👇

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
} point;

point sort[100001];

void merge(point* arr, int first, int mid, int last)
{
    int i, j, k;
    i = first;
    j = mid + 1;
    k = first;

    while (i <= mid && j <= last) {
        if (arr[i].x < arr[j].x)
            sort[k++] = arr[i++];
        else if (arr[i].x > arr[j].x)
            sort[k++] = arr[j++];
        else {
            if (arr[i].y < arr[j].y)
                sort[k++] = arr[i++];
            else if (arr[i].y > arr[j].y)
                sort[k++] = arr[j++];
        }
    }

    if (i <= mid) {
        while (i <= mid) 
            sort[k++] = arr[i++];
    }
    else {
        while (j <= last) 
            sort[k++] = arr[j++];
    }
    for (k = first; k <= last; k++)
        arr[k] = sort[k];
}

void mergesort(point* arr, int first, int last) {
    int mid;
    if (first < last) {
        mid = (first + last) / 2;
        mergesort(arr, first, mid);
        mergesort(arr, mid + 1, last);
        merge(arr, first, mid, last);
    }
}

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

    point* arr = (point*)malloc(sizeof(point)*n);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &arr[i].x, &arr[i].y);
    
    mergesort(arr, 0, n-1);
    for (int i = 0; i < n; i++)
        printf("%d %d\n", arr[i].x, arr[i].y);

    return 0;
}