[Algorithm] 좌표정렬(Comparable, compareTo)

설명

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

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

 

입력

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

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

 

출력

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

 

입력	출력
5 2 7 1 3 1 2 2 5 3 6	1 2 1 3 2 5 2 7 3 6

 

* 객체를 사용자의 기준에 따라 비교하여 정렬 하기 위해서는

Comparable와 Comparator를 사용하는 방법이 있다.

이들은 모두 인터페이스(Interface) 이며 반드시 내부의 선언된 메서드를 꼭 재정의(Override)해야 한다.

 

Comparable는 compareTo(T o1) 메소드를 재정의(Override)을 해주어야 하고 -> 일반적인 정렬

Comparator는 compare(T o1, T o2) 메소드를 재정의(Override) 해주어야 한다. -> 그외 사용자 기준 정렬

 

오늘은 Comparable 인터페이스의 compareTo 메서드를 오버라이드하여 풀어본다.

 

 

 

풀이.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Point implements Comparable<Point>{
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Point o) {
        // 1. call한 자신객체와 매개변수로 넘어온 o객체를 비교한다.
        // 2. this.x에서 o.x을 뺀 return값이 양수일 경우 자리를 교체한다. 그외는 제자리에 위치한다. -> 오름차순
        // 3. 반대로 내림차순으로 정렬하고 싶다면 o.x에서 this.x의 값을 빼면된다.
        if (this.x == o.x) { // x좌표의 값이 같으면 y좌표의 값으로 정렬
            return this.y - o.y;
        } else { // 그외 x좌표를 기준으로 정렬
            return this.x - o.x;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Point> arr = new ArrayList<>(); // Point객체를 담을 ArrayList를 생성한다.
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            arr.add(new Point(x, y)); // ArrayList에 Point객체를 생성해서 담아준다.
        }
        // overrride한 compareTo의 구현에 따라 sort가 정렬을 해준다.
        Collections.sort(arr);
        for(Point o : arr) System.out.println(o.x + " " + o.y);
    }
}

 

1. Comparable의 인터페이스를 구현한 클래스의 기본정렬 순서는 작은값에서 큰값으로 오름차순으로 정렬된다.

2. compareTo() 메서드는 개발자가 직접 호출하는게 아니라 Comparable 인터페이스가 구현된 클래스 객체들이

담겨 있는 배열을 .sort()시 자동으로 호출되면서 각각 객체들의 비교를 수행한다.

 

---

 

정리 : 

Comparable은 자기 자신과 매개변수의 객체를 비교한다.