[C] 백준 11651번 : 좌표 정렬하기2

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

11651번: 좌표 정렬하기 2

---

문제 접근

https://codinghejow.tistory.com/30 동일하다.

느낀점

 사실 이전 문제에서 아주 조금만 수정하면 되는 코드이다.

코드

#include <stdio.h>

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

point arr[100001];
point sorted[100001];

void merge(point arr[], int start, int mid, int last) {
	int i, j, k;
	i = start;
	j = mid + 1;
	k = start;

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

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

	for (int i = start; i <= last; i++) {
		arr[i] = sorted[i];
	}
}

void merge_sort(point arr[], int start, int last) {
	int mid;
	if (start < last) {
		mid = (start + last) / 2;
		merge_sort(arr, start, mid);
		merge_sort(arr, mid + 1, last);
		merge(arr, start, mid, last);
	}
}

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

	merge_sort(arr, 0, n - 1);

	for (int i = 0; i < n;i++) {
		printf("%d %d\n", arr[i].x, arr[i].y);
	}


	return 0;
}