BOJ 11650 (좌표 정렬하기)

#include <stdio.h>
int tmp_x[100000];
int tmp_y[100000];
void merge(int x[], int y[], int left, int right) {
	int L = left;
	int mid = (left + right) / 2;
	int R = mid + 1;
	int i = left;

	while (L <= mid && R <= right) {
		if (x[L] < x[R]) {
			tmp_x[i] = x[L];
			tmp_y[i] = y[L];
			i++; L++;
		}
		else if (x[L] > x[R]) {
			tmp_x[i] = x[R];
			tmp_y[i] = y[R];
			i++; R++;
		}
		else {
			if (y[L] < y[R]) {
				tmp_x[i] = x[L];
				tmp_y[i] = y[L];
				i++; L++;
			}
			else {
				tmp_x[i] = x[R];
				tmp_y[i] = y[R];
				i++; R++;
			}
		}
	}

	if (L > mid) {
		for (int j = R; j <= right; j++) {
			tmp_x[i] = x[j];
			tmp_y[i++] = y[j];
		}
	}
	if (R > right) {
		for (int j = L; j <= mid; j++) {
			tmp_x[i] = x[j];
			tmp_y[i++] = y[j];
		}
	}
	for (int j = left; j <= right; j++) {
		x[j] = tmp_x[j];
		y[j] = tmp_y[j];
	}
}

void mergeSort(int x[], int y[], int left, int right) {
	if (left == right) return;
	int mid = (left + right) / 2;

	mergeSort(x, y, left, mid);
	mergeSort(x, y, mid + 1, right);
	merge(x, y, left, right);
}
int main() {
	int N;
	scanf("%d", &N);
	int x[100000];
	int y[100000];

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

	mergeSort(x, y, 0, N-1);

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

https://reakwon.tistory.com/38?category=308657

좌표를 정렬하는 문제다. 근데, 가장 쉬운 버블 정렬이나 선택 정렬로는 시간제한 때문에 불가능하다. 이런 종류 알고리즘의 시간복잡도는 O(n^2)이다. 그래서 O(nlogn)인 정렬 알고리즘을 사용해야한다. 퀵 정렬, 힙 정렬이 있지만 가장 많이 들어본 합병 정렬을 선택했다.

1학년 때 잠깐 배우긴 했는데, 구현하는데 너무 어려웠던 걸로 기억한다. 그래서 위의 사이트 보면서 구현했다.

mergeSort 함수에서는 재귀적으로 계속 정렬할 배열을 나눈다. 기준값인 mid를 구하고 이를 토대로 나눈다. 만약 다 나눠졌다면 left와 right가 같아서 return 되어 재귀를 종료할 것이다. 그리고 merge 함수를 실행한다. merge는 다 나누어진 각 배열들의 원소의 크기를 비교하며 다시 합치는 과정이다.

해당 문제에서는 좌표를 정렬해야 하므로 x, y 배열을 따로 선언하고 x의 크기로 정렬하고, 같다면 y의 크기로 정렬하게 구현했다.