백준 11650 좌표 정렬하기[JAVA]

문제 해석

• 이번 문제는 첫째줄에 입력받을 숫자의 쌍(x, y)의 개수(N)을 입력받는다.
• N개의 개수만큼 숫자의 쌍(x, y)을 한줄씩 입력받아.
• 숫자의 쌍에 x의 크기를 기준으로 작은 수 -> 큰 수로 정렬한다. (단, x가 같다면 y를 비교하여 y가 작은 수 -> 큰 수 이도록 정렬한다.)

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st ;

        int N = Integer.parseInt(br.readLine());
        int[][] arrays = new int[N][2];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arrays[i][0] = Integer.parseInt(st.nextToken());
            arrays[i][1] = Integer.parseInt(st.nextToken());
        }
        br.close();

        Arrays.sort(arrays, (num1, num2) -> {
            return num1[0]!=num2[0] ? num1[0]-num2[0] : num1[1]-num2[1];
        });

        for(int i = 0; i < N; i++){
            bw.write(arrays[i][0] + " " + arrays[i][1] +"\n");
        }

        bw.flush();
        bw.close();


    }
}

• 나는 숫자의 쌍이라는 말을 보자마자 2차원 배열로 x는 열이 0번째 요소, y는 열이 1번째 요소로 구분해서 비교해야겠다는 생각을 해서, 2차원 배열을 사용하여 정렬하였다.
• 사실 이 코드에서는 핵심코드가 딱 하나 있다.

  Arrays.sort(arrays, (num1, num2) -> {
       return num1[0]!=num2[0] ? num1[0]-num2[0] : num1[1]-num2[1];
  });

• 바로 이 람다식인데, 2차원 배열을 어떻게 하면 정렬할 수 있는 방법을 찾다가 발견한 것이다.

 public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

• sort를 타고 들어가니 이러한 메소드가 존재했다. T[] a는 위에서 보다시피 arrays를 넣은것이고, 여기서 중요하게 봐야하는 것은 Comparator인데 이것에 대한 설명은 아래와 같다.

Comparable vs. Comparator

• 객체를 비교할 수 있도록 도와주는 인터페이스이다.
• 이 문제에서의 배열은 x,y 총 2개의 값씩 가지고 있기 때문에, 무엇으로 비교할지 지정하지 않으면 문제가 생긴다.
• 이러한 문제점을 해결하기 위해 사용하는 것이 Comparable 또는 Comparator이다.
• 그렇다면, Comparable와 Comparator 차이점은 무엇일까?
• Comparable의 비교하는 메소드 compareTo(T o)는 보시다시피 매개변수가 한개이다.
• Comparator의 비교하는 메소드 compare(T o1, T o2)은 딱 보다시피 매개변수가 두개이다.

=> 즉, Comparable은 매개변수가 1개니까 자기 자신과 매개변수 객체를 비교하는 것이고,
Comparator은 매개변수가 2개이니까 그 두 매개변수의 객체를 비교한다는 것이다.

int[][] arrays = [[1, 2], [1 ,3], [1, 1]]
//1.
Arrays.sort(arrays, new Comparator<Integer>() {
  @Override
  public int compare(int num1, int num2) {
     return num1[0]!=num2[0] ? num1[0]-num2[0] : num1[1]-num2[1];
  }
});

//2.
  Arrays.sort(arrays, (num1, num2) -> {
       return num1[0]!=num2[0] ? num1[0]-num2[0] : num1[1]-num2[1];
  });

-> 다시 정리하자면, ①과 ②번은 같은 식이다.
-> 해당 array를 입력받고 그 arrays들의 요소들을 비교하는데, 만약 Comparator에 들어간 num1과 num2을 비교했을시. num1의 0번째요소(=x)과 num2의 0번째요소(=x)가 같다면 y를 비교하고, 다르면 x를 비교하는데 비교하는 식은 num1 - num2이다. 만약이 값(num1 - num2)이 양수이면 자리를 바꾸고, 만약 음수 혹은 0이면 배열의 자리를 바꾸지 않는다.

결과

느낀점

• Comparable와 Comparator은 처음 접하던 것이었는데, 가져다 쓰는 것보다 그 인터페이스를 이해하는 것이 더 어려웠다. (보통 그렇겠지만)
• 근데 Comparable와 Comparator을 쓸 경우 자원(메모리와 시간)을 많이 써서 보완이 좀 많이 필요한 코드같다. (정답이긴 하지만)