백준 정렬 - 11651번 : 좌표 정렬하기 2

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

11651번: 좌표 정렬하기 2

---

import java.io.*;
import java.util.*;
public class Main {
	public static int[][] sorted;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] a = new int[n][2];
		for(int i=0; i<n; i++){
            String[] temp = br.readLine().split(" ");
            a[i][0] = Integer.parseInt(temp[0]);
            a[i][1] = Integer.parseInt(temp[1]);
        }
		br.close();
		sorted = new int[n][2];
        merge_sort(a,0,n-1);
        sorted  =null;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<n; i++) {
        	bw.write(a[i][0]+" "+a[i][1]+"\n");
        }
        bw.close();
    }
	public static void merge_sort(int[][] a, int i, int j) {
		if(i==j) return;
		int mid = (i+j)/2;
		merge_sort(a,i,mid);
		merge_sort(a,mid+1,j);
		merge(a,i,mid,j);
	}
	public static void merge(int[][] a,int i, int mid, int j) {
		int idx = i;
		int start = i;
		int target = mid+1;
		while(start<=mid&&target<=j) {
			if(a[start][1]<a[target][1]) {
				sorted[idx++] = a[start];
				start++;
			}
			else if(a[start][1]==a[target][1]){
				if(a[start][0]<=a[target][0]) {
					sorted[idx++] = a[start];
					start++;
				}
				else {
					sorted[idx++] = a[target];
					target++;
				}
			}
			else if(a[start][1]>a[target][1]){
				sorted[idx++] = a[target];
				target++;
			}
		}
		
		while(start<=mid) {
			sorted[idx++] = a[start];
			start++;
		}
		while(target<=j) {
			sorted[idx++] = a[target];
			target++;
		}
		for(int k = i; k<=j; k++) {
			a[k] = sorted[k]; 
		}
	}
}

바로 전 문제랑 동일한 문제이다.