좌표정렬

 

오늘 이렇게 오랜만에 알고리즘 게시글을 남기는 이유는 중요한 것을 배워서 기록하기 위함이다.

바로 객체 정렬을 위해 Comparable 인터페이스를 사용했기 때문이다.

 

 

좌표 정렬에 관한 문제다.

 

설명 

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

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

 

입력

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

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

 

출력

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

 

먼저 코드는 아래와 같다.

 

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) {
        if(this.x==o.x)return this.y-o.y;
        else return this.x-o.x;
    }
}


public class Unit6{

    public static void main(String[] args)  {
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        ArrayList<Point> arr=new ArrayList<>();
        for(int i=0;i<num;i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            arr.add(new Point(x,y));
        }
        Collections.sort(arr);
        for (Point o : arr) {
            System.out.println(o.x+" "+o.y);
        }
    }
}

 

먼저 중요하다고 생각하는 부분만 작성해보겠다.

 

1. 우선 우리는 정렬할 객체, 즉 x와 y의 값을 가지는 좌표 클래스를 만든다.
2. 그러면 이 정렬할 객체에 Comparable 인터페이스를 implements 한다.
3. 그 이후 정렬할 때 사용할 comepareTo 메소드를 오버라이딩한다.
4. 이 후 오버라이딩한 CompareTo 메소드 코드를 작성한다.
5. Collections.sort를 사용하면 CompareTo 메소드에 작성한 코드대로 정렬이 되므로 Collections.sort를 사용한다.

 

참고 - Comparable은 기본 정렬기준을 구현하는데 주로 사용한다!!! 빗ㅅ한 Comparator 인터페이스는 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용한다. 이는 추후에 한번 다루어보겠다.

 

이제 오버라이딩한 우리 compareTo 메소드에 대해 살펴보겠다.

 

 @Override
    public int compareTo(Point o) {
        if(this.x==o.x)return this.y-o.y;
        else return this.x-o.x;
    }

 

먼저 우리는 오름차순으로 정렬할 것이다! 이 점을 명시하자.

결론부터 말하자면

 

• return 값이 음수, 0이면 객체의 자리가 바뀌지 않는다.
• return 값이 양수면 두 객체의 자리가 바뀐다.

 

우선 x값이 같으면 y 값으로 비교한다. 

this 객체는 현재 객체이고 o 객체는 다음에 오는 객체다.

즉 오름차순으로 정렬하는 우리 문제에서는 this 객체가 다음에 오는 o 객체보다 더 작은 수이다.

 

즉 (2,3) (3,3) (4,4) 이렇게 보고 this 객체가 (3,3)이라고 생각해보자. 그러면 다음에 오는 (4,4) o객체보다 더 작다는 것을 확인할 수 있다.

 

이제 기억할 것은 리턴값이 양수면 자리가 교체되는 것이다.

여기서 우리는 this 객체 좌표의 값이 더 크면 두 객체(좌표)의 자리를 뒤집어야한다.

그러므로 this 객체 좌표에서 뒷 좌표를 빼서 나오는 값을 리턴해서 정렬에 대한 기준을 잡아야한다.

this 객체가 더 크면 오름차순이 아니다. -> this 객체에서 o객체를 빼서 양수가 나오면 this 객체가 더 크므로 자리를 바꿔야한다. 이렇게 판단할 수 있기 때문이다. 그러므로 코드를 저렇게 작성했다.

이렇게 오버라이딩한 compareTo 메소드를 바탕으로 문제를 해결했다.

 

잘 기억해두자...