[C]백준 12.정렬: 11650

백준 11650

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_SIZE 100001
int sorted[MAX_SIZE][2];
int arr[100001][2];

void merge(int list[][2], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;

	while (i <= mid && j <= right) {
		if (list[i][0] < list[j][0]) {
			sorted[k][0] = list[i][0];
			sorted[k++][1] = list[i++][1];
		}
		else if (list[i][0] > list[j][0]) {
			sorted[k][0] = list[j][0];
			sorted[k++][1] = list[j++][1];
		}
		else {
			if (list[i][1] < list[j][1]) {
				sorted[k][0] = list[i][0];
				sorted[k++][1] = list[i++][1];
			}
			else {
				sorted[k][0] = list[j][0];
				sorted[k++][1] = list[j++][1];
			}
		}
	}
	if (i > mid) {
		for (l = j; l <= right; l++) {
			sorted[k][0] = list[l][0];
			sorted[k++][1] = list[l][1];
		}
	}
	else {
		for (l = i; l <= mid; l++) {
			sorted[k][0] = list[l][0];
			sorted[k++][1] = list[l][1];
		}
	}
	for (l = left; l <= right; l++) {
		list[l][0] = sorted[l][0];
		list[l][1] = sorted[l][1];
	}

}

void merge_sort(int list[][2], int left, int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}

int main() {
	int n;

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

	merge_sort(arr, 0, n - 1);
	for (int i = 0; i < n; i++) {
		printf("%d %d\n", arr[i][0], arr[i][1]);
	}
	return 0;
}

정렬해야 할 점의 개수 N의 최대값이 100,000이기에 시간복잡도가 nlogn인 합병정렬을 이용해 풀었다. 기존의 합병정렬 코드에서 merge()함수부분을 살짝 변경하였다. 좌표의 경우 이차원배열을 이용해 arr[i][0]에는 x좌표를, arr[i][1]에는 y좌표를 넣어주었다. x좌표가 우선적으로 비교되고, x좌표가 같을 시 y좌표가 비교되기에 arr[i][0]을 먼저 비교하고 만약 arr[i][0]이 같을 경우엔 arr[i][1]을 비교하는 방식으로 코드를 작성했다.

 

다른 사람의 코드를 살펴봤는데 좌표를 구조체를 이용해 표현하고, qsort함수를 이용해 푼 코드가 개인적으로 제일 좋아보였다. 아래는 그 코드이다. 다음에는 이렇게 풀면 좋을 것 같다. 

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

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

int compare(const void* first, const void* second)
{
	coord* a = (coord*)first;
	coord* b = (coord*)second;

	if (a->x < b->x)
		return -1;
	else if (a->x > b->x)
		return 1;
	else
	{
		if (a->y < b->y)
			return -1;
		else
			return 1;
	}
	return 0;
}

int main()
{
	int i, n;
	coord* list;

	scanf("%d", &n);
	list = (coord*)malloc(n * sizeof(coord));

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

	qsort(list, n, sizeof(list[0]), compare);


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

<출처: https://sedangdang.tistory.com/16>