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

백준 온라인 저지(BOJ) 11650번 좌표 정렬하기

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

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

 

1. 문제

2차원 평면 위의 점 N개가 주어짐 [1 ~ 100,000]

x가 증가하는 순으로, 같으면 y가 증가하는 순서로 정렬하여 출력

각 좌표의 범위는 [-100,000 ~ 100,000] 이고, 위치가 같은 점은 없음

 

2. 풀이

Merge Sort 를 학습하면서 풀어보았습니다.

기본적인 Merge Sort 코드와 거의 유사한데 아래 2가지만 다릅니다.

1) 그냥 배열이 아닌 _p(point) struct 를 만들어서 배열에 사용

2) compare 함수를 만들어서 좌표 크기 비교 시 사용

 

Merge Sort 에 대한 개념을 먼저 학습하시고,

좋은 Code 찾아서 몇 차례 반복하여 작성해보시면 어렵지 않게 익힐 수 있습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11650_좌표 정렬하기
https://www.acmicpc.net/problem/11650
*/
#include <cstdio>

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

// a 가 작으면 음수, b 가 작으면 양수
int compare(_p a, _p b) { return a.x == b.x ? a.y - b.y : a.x - b.x; }

void mSort(int s, int e) { // [s ~ 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("11650.txt", "r", stdin);
#endif // _WIN32
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i].x);
		scanf("%d", &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;
}