[C]백준 12.정렬: 11651

백준 11651

내코드

#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][1] < list[j][1]) {
			sorted[k][0] = list[i][0];
			sorted[k++][1] = list[i++][1];
		}
		else if (list[i][1] > list[j][1]) {
			sorted[k][0] = list[j][0];
			sorted[k++][1] = list[j++][1];
		}
		else {
			if (list[i][0] < list[j][0]) {
				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;
}

11650 문제와 아주 유사한 문제였다. 그래서 그 코드에서 merge()함수의 정렬하는 기준만 바꾸었다. 좌표는 이차원배열을 이용해 표현했고, 합병정렬을 이용해 문제를 풀었다.

 

마찬가지로 이 문제도 다른사람의 코드를 살펴봤는데 좌표를 구조체로 표현하고, 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->y < b->y)
		return -1;
	else if (a->y > b->y)
		return 1;
	else
	{
		if (a->x < b->x)
			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>