[BOJ/Step12] 11650 : 좌표 정렬하기 (JAVA)

www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

---

문제

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

 

입력

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

 

출력

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

 

예제 입력 

5

3 4

1 1

1 -1

2 2

3 3

 

예제 출력 

1 -1

1 1

2 2

3 3

3 4

---

풀이

나는.. 이게 정렬 파트에 있고.. 앞에 여러 정렬들을 쓰라고 해서.. 그것들을 이용해서 푸는줄 알고......

x좌표를 기준으로 정렬하고 x좌표가 같은 것들끼리 다시 y좌표를 기준으로 정렬하는 방법으로 풀려고 아주 머리 쥐어싸매며 코딩했는데..

풀고 난 뒤에 찾아보니 comparator를 재정의해서 푸는 방법이 있더라 하하

compare 알았는데 왜 떠올리지 못했는지..?

일단 머리 쥐어싸맨 시간이 아까우니 내가 푼 멍청한 방법도 함께 기록해둔다..

 

- 멍청한 방법

기본 합병정렬 메소드를 수정하여 2차원 배열을 각각 x를 기준으로, y를 기준으로 정렬하도록 한다.

1. int[n][2] 크기의 배열 xy를 선언, 입력받은 값을 x는 xy[0]에, y는 xy[1]에 저장한다

2. 배열 xy를 x를 기준으로 정렬한다

3. x를 기준으로 정렬된 배열을 x가 같은 것끼리 묶어서 y를 기준으로 정렬해준다.

   3-1. left = 0, right = 0으로 시작하여 xy[i][0] 와 xy[i+1][0] 을 비교

   3-2. 같지 않으면 right에 i를 저장한 후 0 ~ i 사이를 y를 기준으로 정렬한다.

   3-3. left에 i+1을 저장한 후 반복

   3-4. for문 수행이 끝나면 left~배열의 끝까지 y를 기준으로 정렬한다.

          ( 마지막엔 xy[i][0] 와 xy[i+1][0] 가 다른 부분을 만나지 못하고 끝나 y정렬 되지 않았기 때문에 )

4. 정렬된 배열 xy 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B11650_1 {
	
	static int[][] buff;
	
	static void mergeSortX(int[][] a, int left, int right) {
		if(left < right) {
			int i;
			int center = (left + right) /2;
			int p = 0;
			int j = 0;
			int k = left;
			
			mergeSortX(a, left, center);
			mergeSortX(a, center + 1, right);
			
			for(i = left; i <= center; i++) {
				buff[p][0] = a[i][0];
				buff[p++][1] = a[i][1];
			}

			while(i <= right && j < p) {
				a[k][0] = (buff[j][0] <= a[i][0]) ? buff[j][0] : a[i][0];
				a[k++][1] = (buff[j][0] <= a[i][0]) ? buff[j++][1] : a[i++][1];
			}
					
			while(j < p) {
				a[k][0] = buff[j][0];
				a[k++][1] = buff[j++][1];
			}
		}
	}
	
	static void mergeSortY(int[][] a, int left, int right) {
		if(left < right) {
			int i;
			int center = (left + right) /2;
			int p = 0;
			int j = 0;
			int k = left;
			
			mergeSortY(a, left, center);
			mergeSortY(a, center + 1, right);
			
			for(i = left; i <= center; i++) {
				buff[p][0] = a[i][0];
				buff[p++][1] = a[i][1];
			}

			while(i <= right && j < p) {
				a[k][0] = (buff[j][1] <= a[i][1]) ? buff[j][0] : a[i][0];
				a[k++][1] = (buff[j][1] <= a[i][1]) ? buff[j++][1] : a[i++][1];
			}
					
			while(j < p) {
				a[k][0] = buff[j][0];
				a[k++][1] = buff[j++][1];
			}
		}
	}
	
	static void mergeSort(int[][] a, int n) {
		buff = new int[n][2];
		mergeSortX(a, 0, n-1);
		
		int left = 0, right = 0;
		for(int i = 0; i < n-1; i++) {
			if(a[i][0] != a[i+1][0]) {
				right = i;
				mergeSortY(a, left, right);
				left = i+1;
			}
		}
		mergeSortY(a, left, n-1);
		buff = null;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[][] xy = new int[n][2];
		
		StringTokenizer st;
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			xy[i][0] = Integer.parseInt(st.nextToken());
			xy[i][1] = Integer.parseInt(st.nextToken());
		}
		
		mergeSort(xy, n);
		
		for(int i = 0; i < n; i++) {
			System.out.println(xy[i][0] + " " + xy[i][1]);
		}
	}
}

 

- comparator 사용한 방법

import java.io.*;
import java.util.*;

public class B11650_2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[][] xy = new int[n][2];
		
		StringTokenizer st;
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			xy[i][0] = Integer.parseInt(st.nextToken());
			xy[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(xy, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]){
		            return o1[1] - o2[1];
		        }else{
		            return o1[0] - o2[0];
		        }
			}
		});
		
		for(int i = 0; i < n; i++) {
			System.out.println(xy[i][0] + " " + xy[i][1]);
		}
	}
}