BOJ/11650

좌표 정렬하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stack>
#include <algorithm>


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

int compare(const void *p1,const void *p2) {
	const point* a1, * a2;
	a1 = (point*)p1;
	a2 = (point*)p2;
	
	if (a1->x > a2->x) {
		return 1;
	}
	else if (a1->x == a2->x) {
		if (a1->y > a2->y) {
			return 1;
		}
		else {
			return -1;
		}
	}
	else {
		return -1;
	}
}

int main() {

	int x;
	scanf("%d", &x);

	point points[100000];

	for (int i = 0; i < x; i++) {
		scanf("%d %d", &points[i].x, &points[i].y);
	}
	
	qsort(points, x, sizeof(point), compare);
	
	for (int i = 0; i < x; i++) {
		printf("%d %d\n", points[i].x, points[i].y);
	}
	
	return 0;
}

계산량이 많기 때문에 그냥 내멋대로 for문 사용하여 버블정렬 시켜버리면 어떻게 하던 시간초과가 떠버린다.(시간복잡도 : O(nlogn))

따라서 다른 정렬 방법을 사용해야 함.

여러 정렬 방법 중에서 c의 stdlib에서 지원하는 qsort를 사용(시간복잡도 : O(nlogn))

void qsort(
   void *base,
   size_t number,
   size_t width,
   int (__cdecl *compare )(const void *, const void *)
);

출처 : Microsoft

qsort는 compare 함수를 따로 지정해 주어야 한다.

compare함수

++추가++

c++의 <algorithm>라이브러리는 이것보다 쉬운 방법으로 sort()를 제공해준다.

sort(배열 시작, 배열 끝)을 입력해주면 기본적으로 오름차순으로 정렬이 가능하다.

ex) sort(arr , arr + 10)

여기에 추가로 compare함수를 통해 c의 qsort와 같이 조건을 추가할 수 있다.

ex) bool compare(int a, int b) {  return a > b;  } //내림차순