[Inflearn] 자바 알고리즘 문제풀이 #06-07 7. 좌표 정렬

문제

설명

N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.

정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.

 

입력 

첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.

두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.

 

출력 

N개의 좌표를 정렬하여 출력하세요.

예시 입력 1 

5
2 7
1 3
1 2
2 5
3 6

예시 출력 1

1 2
1 3
2 5
2 7
3 6

 

 

 

내 풀이

import java.util.*;

public class Main6_7 {
    public int[][] Solution(int n, int[][] arr) {
        //2차월 배열 정렬 0번째 열 다음 1번째 열 기준(다중 배열 정렬)
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1]; // 오름차순 o1[1] - o2[1] 내림차순 o2[1] - o1[1]
                } else {
                    return o1[0] - o2[0];
                }
            }
        });
        return arr;
    }

    public static void main(String[] args) {
        Main6_7 T = new Main6_7();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        T.Solution(n, arr);
        for (int i = 0; i < n; i++) {
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }
}

2차원 배열을 정렬할 때 원하는 정렬 기준으로 정렬하고 싶으면

Comparator 익명클래스 구현 - compare() 메서드를 오버라이드해서 사용하면 된다.

아래 알게된 점에 관련 포스팅 링크를 올려두겠다.

 

 

 

선생님 풀이

import java.util.*;

class Point implements Comparable<Point> { // Point 객체를 정렬
    public int x,y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Point o){
        if(this.x == o.x) return this.y-o.y; // 오름차순 정렬
        else return this.x-o.x;
    }
}

public class Main6_7 {
    public static void main(String[] args) {
        Main6_7 T = new Main6_7();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Point> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            arr.add(new Point(x, y));
        }
        Collections.sort(arr); // 재정의한 compareTo에 의해서 정렬됨
        for(Point o : arr) System.out.println(o.x + " " + o.y);
    }
}

좌표(Point 객체)를 사용하거나 Point 객체를 사용해 정렬할 때 

comparable이라는 인터페이스의 구현클래스로 Point를 만들고, compareTo()를 재정의 하는 방법이 많이 사용된다. ⭐️⭐️

외워두자 !

 

 

 

결과

 

 

 

알게된 점

1. 2차원 배열 정렬

https://rookie-programmer.tistory.com/84

[JAVA] 자바 2차원 배열 정렬 Comparator

 

 

2. compareTo 재정의 정렬

return 값이 음수가 나오게 한다.

1) 오름차순(this.x - o.x 혹은 this.y-o.y)

오름차순일 경우에는 this 객체는 값이 작은 것, o 객체는 값이 큰 것으로 정의된다. 따라서 this 객체가 1 2, o 객체가 1 3

오름차순 ==> this.y - o.y = -1인 음수값이 나오기 때문에 오름차순으로 정렬

 

2) 내림차순(o.x - this.x 혹은 o.y - this.y)

내림차순일 경우에는 this 객체는 값이 큰 것, o 객체는 값이 작은 것으로 정의된다. 따라서 this 객체가 1 3, o 객체가 1 2

내림차순 ==> o.y - this.y = -1인 음수값이 나오기 때문에 내림차순으로 정렬

 

 

헷갈린다면 this는 현재 것, o는 새로 들어오는 것이라 생각한 다음에

this - o라고 적으면 오름차순, o - this라고 적으면 내림차순으로 외워버리자.