[algorithm] 정렬 백준 11651 좌표 정렬하기2

◾문제

좌표 정렬하기 2

레벨: 실버5

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

 

 

◾풀이

Comparator를 이용한 정렬이 익숙하다면 어렵지 않게 풀 수 있는 문제이다.

 

- 입력받기

N개의 x,y 좌표를 입력받으므로 입력받은 N을 기준으로, Nx2크기의 2차원 배열을 선언하여 입력받는다.

int[][] arr = new int[N][2];

 

- 정렬하기

배열을 정렬하는 것이므로 'Arrays.sort() 를 이용한다.' 라고 생각할 수 있으나 이는 2차원 배열이므로 만일 정렬을 해야한다면 한 행씩 정렬을 해야한다.  Arrays.sort()는 직접 2차원 배열을 정렬할 수 없기 때문이다.

 

그러나 일반적인 오름차순 정렬이 아니기 때문에, 문제에서 요구하는 방식으로 정렬을 해야하므로 Comparator를 구현하여 정렬 기준을 세워 2차원 배열을 정렬한다. 

 

 

정렬 기준 세우기

2차원 배열에서 첫 번째 요소는 x좌표, 두 번째 요소는 y좌표이다. int[]타입으로 Comparator를 선언하고, 각 요소를 int[] o1, int[] o2라 하였을 때 o1[0],o2[0]은 배열에서 arr[i][0] i번째 행에서 0번째에 있는 x좌표를 가리킨다. o1[1],o2[1]은 arr[i][1] i번째 행에서 1번째에 있는 y좌표를 가리킨다.

 

첫 번째 기준의 경우 y좌표가 증가하는 순이므로 y좌표가 같지 않을 때 오름차순으로 정렬을 해야한다.

if(o1[1]!=o2[1]) // y좌표가 같지 않다면
    return o1[1]-o2[1]; // 오름차순 정렬

 

왜 o1[1] - o2[1]을 빼는 것인지 이해가 안간다면 아래 compare메서드 동작 방식을 참고하자. o1[1] 은 앞의 요소, o2[1]은 뒤의 요소를 가리킨다. 앞의 요소에서 뒤의 요소를 뺐을 때 앞의 요소가 더 크다면 양수를 반환한다.(return) 양수를 반환하면 compare메서드는  o1과 o2의 순서를 바꾼다. 즉 앞의 요소가 더 크다면 순서를 바꿔 뒤로 가게하여 작은 것이 앞으로, 큰 것은 뒤로 가게 만들어 오름차순이 되게 한다. 이런 원리로 오름차순이 되는 것이고 만일 내림차순을 한다면 반대로 o2[1] - o1[1] 과 같이 선언해주면 된다. 

 

두 번째 기준의 경우 x좌표가 증가하는 순인데, 마지막 조건이기 때문에 x좌표가 같지 않은 경우의 조건(if문)을 넣어줄 필요없이 아래와 같이 선언하여 x좌표를 기준으로 오름차순이 되도록 한다.

 

else
   return o1[0]-o2[0];

 

 

🤔Comparator의 compare메서드 동작방식

compare(a,b) a와 b 두 요소가 주어졌을 때

- 메서드의 반환값이 0보다 작거나 같은 경우: a와 b의 상대적인 순서를 유지한다. (변화 X)

- 메서드의 반환값이 0보다 큰 경우: a와 b의 순서를 바꾼다. (변화 O)

 

 

 

 

◾정답 코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
//좌표 정렬하기 2
public class P11651 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]!=o2[1])
                    return o1[1]-o2[1];
                else
                    return o1[0]-o2[0];
            }
        });
        for (int i = 0; i < N; i++) {
            bw.write(arr[i][0]+" "+arr[i][1]+"\n");
        }
        bw.flush();
        bw.close();
    }
}