[백준] [C] 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개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1

5
3 4
1 1
1 -1
2 2
3 3

예제 출력 1

1 -1
1 1
2 2
3 3
3 4

알고리즘 [ 접근방법 ]

앞서 포스팅한 문제들을 복합적으로 고려해 풀이를 해야만 하는 문제이다. Bubble Sort는 너무 효율이 떨어지고 문제에 주어진 시간제한을 맞출 수 없기 때문에 배제하고 Merge Sort를 사용 할 수 있는데 Merge Sort는 코드가 너무 복잡하고 매번 일일히 구현하기에는 어려움이 있다. 이를 해결 해줄 수 있는 아주 간단한 내장 Sorting 라이브러리를 발견했는데 바로 qsort 함수이다. qsort를 사용하면 바로 해결되는 문제이므로 따로 풀이는 하지않고 코드에 주석으로 남겨놓겠다.

qsort ( = Quick Sort ) 의 코드 구성이나 작동 원리는 따로 알고리즘 파트에 포스팅을 해놓을 테니 이를 참고하길 바란다.
해당 링크 : 퀵 정렬(Qucik Sort)

풀이

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

// x,y 좌표를 표현하기 위한 구조체 설정
typedef struct {
	int x;
	int y;
}coord;

// qsort 함수를 사용하기위한 비교 함수
int compare(const void* a, const void* b) {
	coord* num1 = (coord*)a;   // void 포인터를 coord 포인터로 변환한 뒤 역참조하여 값을 가져옴
	coord* num2 = (coord*)b;   // void 포인터를 coord 포인터로 변환한 뒤 역참조하여 값을 가져옴

	if (num1->x < num2->x) return -1;
	else if (num1->x > num2->x) return 1;
	else {
		if (num1->y < num2->y) return -1;
		else return 1;
	}
	return 0;
}

int main() {
	int num = 0;
	coord* list;

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

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

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

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

	return 0;
}