[백준] 11651 - 좌표 정렬하기 2 (자바/Java) : Merge Sort

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

---

이번에도 merge sort를 이용하여 풀었다. Collection의 sort와 comparable을 이용하면 좀 더 간단하게 될 것 같음!

비교하는 부분만 y 좌표가 같으면 x 좌표를 다시 비교하도록 구현하였다.

package BOJ0726;

import java.util.Scanner;

public class BOJ_11651_좌표정렬2 {
	static int[][] sorted = new int[100001][2];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[][] arr = new int[N][2];
		for (int i = 0; i < N; i++) {
			arr[i][0] = sc.nextInt(); // x
			arr[i][1] = sc.nextInt(); // y
		}

		// merge sort
		mergeSort(arr, 0, N - 1);

		for (int i = 0; i < N; i++) {
			System.out.print(arr[i][0] + " " + arr[i][1] + "\n");
		}

	}

	static int[][] merge(int[][] arr, int l, int mid, int r) {
		int i = l; // 왼쪽 배열의 시작 index
		int j = mid + 1; // 오른쪽 배열의 시작 index
		int k = l; // merge 결과 배열의 index

		while (i <= mid && j <= r) {
			if (arr[i][1] < arr[j][1]) { // y좌표
				sorted[k++] = arr[i++];
			} else if (arr[i][1] == arr[j][1] && arr[i][0] < arr[j][0]) {
				sorted[k++] = arr[i++];
			} else {
				sorted[k++] = arr[j++];
			}
		}

		if (i > mid) {
			for (int right = j; right <= r; right++) {
				sorted[k++] = arr[right];
			}
		} else {
			for (int left = i; left <= mid; left++) {
				sorted[k++] = arr[left];
			}
		}

		// 원래 배열에 복사
		for (int tmp = l; tmp <= r; tmp++) {
			arr[tmp] = sorted[tmp];
		}

		return arr;

	}

	static int[][] mergeSort(int[][] arr, int l, int r) {
		int mid;
		if (arr.length == 1) {
			return arr;
		}

		if (l < r) {
			mid = (l + r) / 2;
			arr = mergeSort(arr, l, mid);
			arr = mergeSort(arr, mid + 1, r);
			arr = merge(arr, l, mid, r);
		}

		return arr;
	}

}