[Baekjoon] Class2 36 - 좌표 정렬하기 [11650]

좌표 정렬하기 [11650번]

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

입력

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

출력

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

생각해볼점

구조체를 이용해 좌표 x,y를 한 쌍으로 받은 후, 퀵 정렬을 이용해 정렬했다.
이 때 compare함수에서 x좌표를 기준으로, x좌표가 같다면 y좌표를 기준으로 오름차순 정렬하도록 했다.

코드 구현

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

typedef struct coordinate
{
	int	x;
	int	y;
} cor;

static int compare(const void *one, const void *two)
{
	cor	a = *(cor *)one;
	cor	b = *(cor *)two;
	
	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	num, idx;
	cor *xy;

	scanf("%d", &num);
	xy = (cor *)malloc(num * sizeof(cor));
	
	idx = -1;
	while (++idx < num)
		scanf("%d %d", &xy[idx].x, &xy[idx].y);

	qsort(xy, num, sizeof(cor), compare);

	idx = -1;
	while (++idx < num)
		printf("%d %d\n", xy[idx].x, xy[idx].y);
	
	free(xy);
	return (0);
}