[백준/BOJ] 11651번 좌표 정렬하기 2 (C/C++)

백준 온라인 저지(BOJ) 11651번 좌표 정렬하기 2
https://www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

* 사용언어 : C언어, C++
 

1. 문제

2차원 평면 위의 점 N개가 주어짐 [1 ~ 100,000]
x가 증가하는 순으로, 같으면 y가 증가하는 순서로 정렬하여 출력
각 좌표의 범위는 [-100,000 ~ 100,000] 이고, 위치가 같은 점은 없음
 

2. 풀이

앞서 풀이한 좌표 정렬하기 1 문제와 거의 유사한 코드로 구현했습니다.
https://rightbellboy.tistory.com/136

[백준/BOJ] 11650번 좌표 정렬하기 (C/C++)

 
차이점은 compare 함수 내부에 x 보다 y 에 우선 순위를 두었다는 점이고,
그 외에는 동일합니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11651_좌표 정렬하기 2
2676KB	64ms
*/
#include <cstdio>

const int LM = 100000;
int n;

struct _p {
	int x, y;
} a[LM + 5], t[LM + 5];

int compare(_p a, _p b) { return a.y == b.y ? a.x - b.x : a.y - b.y; }

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (compare(a[i], a[j]) < 0) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (i = s; i <= e; ++i) a[i] = t[i];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d %d", &a[i].x, &a[i].y);

	mSort(0, n - 1);

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