백준 11650, 11651 <좌표 정렬하기 1,2>

11650번: 좌표 정렬하기 (acmicpc.net)

11650번: 좌표 정렬하기

이 문제는 2차원 좌표평면의 좌표들의 순서를 정렬하는 문제이다. 

첫번째 최우선의 정렬 기준은 x좌표 증가 순, 그리고 x좌표가 같다면 y좌표가 증가하는 순서로 정렬을 하는 것이다.

 

일단 나의 첫번째 시도는 x좌표 따로, y좌표 따로 , 그 다음 이 두 x,y를 합친 배열 따로 총 3가지 배열을 다뤄보자하였다.

고민을 계속하다 보니 xy 좌표 를 따로 배열로 두어 이들을 다루는 것은 상당한 한계가 있다. 당연하게도 x배열이 sorting됨에 따라 xy합친 배열도 움직여야하고, 이 중 x가 같은 경우는 또 합친 배열의 y까지 다시 바꿔줘야하는데 이는 쉽지가 않다. 하려다가 필자는 포기했다.

 

두번째 시도는 2차원 배열로 생성하여 좌표를 다루는것이다. 물론 2차원 배열을 sorting하는것은 쉽지는 않지만 이 포스트에서 소개할 방법이 있다. 바로 comparator을 활용하는 것이다.

자바 [JAVA] - Comparable 과 Comparator의 이해 (tistory.com)

자바 [JAVA] - Comparable 과 Comparator의 이해

comparator에 대한 설명은 내가 자주 참고하는 분의 블로그에 아주 친절하게 설명되어 있다.

일단 comparotor은 Interface이다. 따라서 일반적인 클래스와는 다르게 내재되어 있는 compare() 메소드를 직접 구현해야한다.  즉 사용자가 직접 구현한 compare()대로, 정렬의 방식이 바뀌니 유용하다고 할 수 있다. 

 

Comparator의 type 즉, 아래와 같은 경우 type이 int[]인것을 볼 수 있고, 이를 활용해 compare의 매개변수 또한 int[]이다.

Arrays.sort(arr, new Comparator<int[]>() {		
	@Override
	public int compare(int[] e1, int[] e2) {
		if(e1[0] == e2[0]) {		// 첫번째 원소가 같다면 두 번째 원소끼리 비교
			return e1[1] - e2[1];
		}
		else {
			return e1[0] - e2[0];
		}
	}
});

 

즉 , 2차원 배열에서는  x,y를  하나의 1차원 배열 x 1차원 배열로 관찰을 하곤 하는데 이를 그냥 arrays.sort()를 해버리면 기준이 애매해지기에, 2차원 배열에서의 sort를 Comparator을 int[]로 설정해주면,  이 문제와 같이 x 기준으로 정렬을 할건지, y 기준으로 정렬할건지 사용자 스스로 정렬 규칙을 생성하여 xy 배열 중 한개를 골라 정렬의 기준인 규칙을 사용자화 할 수 있다.

 

x,y좌표를 배열로 구상할때는 arr[n][2]짜리로 하는데, 이때 정렬의 기준을  x로 한다면, x좌표가 담긴 배열은 0번째에 인덱스에 있을 것이다. 예를들어 3,4// 1,2라면 3,1이라는 좌표는 각각 0,0번째, 1,0번째에있겠다. 따라서 각 행의 0번째 인덱스이를 기준으로 잡아야한다. 따라서 위 코드에서 return e1[0] - e2[0] 이부분이 조건문이 만족하지 않을때 else) 일때 x좌표기준으로 정렬을 하겠다는 소리다.

 

여기서 의문점은 저 메소드는 분명 int type을 return할 것이다. 그렇다면 정렬의 방식이 이 return 값에 달렸다는 건데, 일단 기본적으로 자바는 오름차순 정렬이 기본이다. (arrays.sort) return값이 양수라면 오름차순, 0이라면 그대로 , 음수라면 내림차순으로 정렬을 control할 수 있다. 즉 만약 내가 코드 순서를 return e2[0] - e1[0] 이렇게 바꾼다면 정렬의 방향이 바뀌겠다. 

 

결론은, comparator을 쓸때, gpt피셜로는 1차원 배열을 정렬할때는 잘 사용하지 않는다고 한다. 어찌보면 당연..

걍 sort한줄쓰면 끝이니, 하지만 2차원배열과 같이 배열의 구성이 많아져서 한번에 정렬하기 빡세거나 정렬의 기준이 기본 정렬이 아닐때는 comparator을 사용하는 것도 좋은 것 같다. 

 

특히 이 문제와 같은 경우 XY좌표와 같이 정수형 배열이어서 정렬이 직관적이지만, 다른 type을 넣어서 쓸때도 가능하니 이 점 참고해보자!

package 백준;
import java.util.*;
import java.io.*;
public class _11650_좌표정렬하기_simplever {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		//좌표니까 일단 2차원 배열 생성
		int[][] arr = new int[N][2];
		
		StringTokenizer st;
		
		//구분자가 1 0 일테니 st에는(br.readline만해줘도  ㅇㅋ)
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
	//정렬을 특정 방식으로 고수하여 정렬하기 위해서  0번쨰 인덱스 즉, x값이 같다면 1번째 인덱스 y번째로 배열 정렬하고
		//0번째 인덱스 x값이 다르면 x값을 sort해야하기에 return e1[0]-e2[0]로.
			Arrays.sort(arr, new Comparator<int[]>() {		
				@Override
				public int compare(int[] e1, int[] e2) {
					if(e1[0] == e2[0]) {		// 첫번째 원소가 같다면 두 번째 원소끼리 비교
						return e1[1] - e2[1];
					}
					else {
						return e1[0] - e2[0];
					}
				}
			});
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i< N ; i++) {
			sb.append(arr[i][0] + " " + arr[i][1]).append('\n');
		}
		System.out.println(sb);

	}

}