좌표 정렬 알고리즘 공부하기 feat. Comparable interface, 백준 11650 좌표 정렬하기

1. 객체 비교는 왜 필요한가?

사실 지금까지의 '비교' 의 개념은 객체가 아닌 primitive type 에서만 적용되는 개념이었다. 또한 기본형 타입에서의 모든 비교는 아주 단순했다. 그냥 부등호로 크기가 결정되어버리니까.

그러나 자바를 다루다보면 '객체' 를 비교해야 하는 경우가 있다. 이때는 어떻게 비교하면 좋을까? 예시를 들어보자.

학생 객체 a, b, c 가 있다. a 는 1등급 97점, b 는 1등급 92 점, c 는 2등급 87 점이다. 나는 이 학생 객체들을 정렬하고 싶다. 정확히는 등급은 오름차순으로 하되, 같은 등급이면 점수를 내림차순으로 정렬하고 싶다.

 

package algorithm;

public class Test {
    public static void main(String[] args)  {

        Student a = new Student(1, 97);    // 1등급 97점
        Student b = new Student(1, 92);    // 1등급 92점
        Student c = new Student(2, 87); // 2등급 87점

      /*
       		당연하지만 단순히 기본형 처럼 단순히 부등호로는 비교가 불가능하다.
            그렇다면 어떻게 비교해야할까? 뭘 기준으로 비교해야할까?
            이런 의문이 바로 객체 비교의 시작이된다.
            
            생각해보면 마치 SQL 문의 order by 와 비슷하다는 생각도 든다.
            결국 order by 도 특정 컬럼끼리 '비교'해서 '정렬' 하는 것이니까.
	
       */

    }
}

class Student {

    int grade; // 등급
    int score; // 점수

    Student(int grade, int score) {
        this.grade = grade;
        this.score = score;
    }
}

이럴때 바로 객체를 비교하기 위한 Comparable Interface 가 등장한다.

 

2. Comparable Interface

Comparable 인터페이스 자체는 단 하나의 메서드만을 갖는다. 따라서 해당 인터페이스를 구현한 구현 클래스 역시 단 하나의 메서드만 구현해주면 된다. 근데 여기서부터는 살짝...아니 개인적으로 개념 잡기에 정말 많이 힘들었다.

 

인터페이스의 메서드는 CompareTo(Object o) 라는 메서드이다. 말 그대로 매개변수가 되는 객체와 인터페이스를 구현하는 자기자신 객체와 비교! 를 해주는 메서드이다. 근데 좀 이상한 부분이 있다. 바로 return 하는 값이 int 형이라는 점이다. 왜?? 대체 왜? 어째서 int 를 return 해주는 걸까? 어떻게 계산이 되면 int 로 return 되는 걸까?

// 메서드는 단 하나!
public interface Comparable<T> {
 
    public int compareTo(T o);
}

int 형을 return 하는 이 메서드를 대체 어떻게 구현하면 되는걸까? 이 부분이 바로 개념잡기가 필요한 부분이자 개인적으로는 굉장히 어려웠던 부분이다. 그리고 ComparableTO 메서드의 구현에 대해서 설명하기 위해서는 먼저 '비교' 을 구현하는 방법에 대해서 알아야 한다.

왜냐하면 int 형을 return 하는 이유가 곧 '비교'를 구현하기 위한 첫 걸음이기 때문이다.

 

3. ComparableTo 메서드  : return 되는 int 값 알아보기

CompareableTo 메서드를 나라는 객체의 값과 비교 대상이 되는 객체의 값을 비교해서 int 값을 return 해주는 메서드이다.

예를들면 1이 3보다 작다 혹은 5가 3보다 크다 라는걸 코드로 어떻게 구현해야한다. 정확히는 단순한 부등호가 아닌, 다른 방식으로 '비교'해야하고 동시에 int 값이 return 되게 해야한다. 그렇다면 어떻게 비교하면 좋을까? 사실 이 부분 자체는 의외로 간단하다. 바로 자기 자신의 값과 비교 대상이 되는 값의 차를 통해 알아내는 것이다. 

 

예시 1 ) 나는 1 이라는 수이다. 나와 비교 대상이 되는 숫자 3을 비교해서 누가 더 큰지 알아보고 싶다. 그렇다면 '나' 에서 비교 대상이 되는 숫자를 빼보면 된다. 즉 1- 3 을 했을 때 음수값이 나오면 우리는 '나' - 1 - 는 상대방 - 3 - 이 더 작다는 걸 알 수 있다.

 

예시 2 ) 이번에는 조금 레벨 업 해서 돌아와서 '나' 는 숫자 5가 되었다. 이전에 나와 비교했던 상대방 - 3 - 과 비교해보자. 마찬가지로 아주 단순하게 나에서 상대방의 차를 구한다. 그리고 5 - 3 했을 때 값은 양수값이 되는 것을 우리는 알 수 있고 이를 통해 '나' - 5 - 는 상대방 - 3 - 보다 크다 는 것을 알 수 있다.

 

이제 정리해보자.
CompareTo 메서드는 int 를 return 해주는 비교 메서드이다. 결국 int 형을 return 해주고 이를 기준으로 정렬하기 때문에 이 return 해주는 int 값이 정렬의 기준이 되는 것을 알 수 있다.

여기서 리턴되는 int 값은 는 자기 자신 객체와 상대방의 객체를 비교해서 나온 값이여야한다. 정확히는 대상 객체와 넘어오는 객체의 차 값이 해서 int 양수면 내림차순 정렬, 0 이면 그대로, 음수면 오름차순 정렬 의 형태를 취하며 더 자세하게 정리하자면 다음과 같다.

만약 대상 객체 x 와 넘어오는 객체 o 를 비교해서 x - o 가 양수라면 x > o 임을 알 수 있고 이로인해 x-> o 순서가 된다.
만약 대상 객체 x 와 넘어오는 객체 o 를 비교해서 x - o 가 음수라면 x < o 임을 알 수 있고 이로인해 o->x 순서가 된다.

 

 

4. ComparableTo 메서드  : 오름차순, 내림차순

ComparableTo 메서드로 오름차순과 내림차순을 구현하려면 어떻게 해야 할까? 바로 앞에서 보았던 두 수의 차 값이 양수인 경우와 음수인 경우를 기억해야한다.

즉, 오름차순이면 작은수부터 큰 수로 정렬된 것이고 결국 앞의 숫자에서 뒤의 숫자를 빼면 음수값이 나오게 된다.

만약 내림차순이라고 한다면 큰 수에서 작은 수로 정렬된 것이고 결국 앞의 숫자에서 뒤의 숫자를 빼면 양수값이 나오게 된다.

 

예시 1) 5,4,3,2,1 배열이 있다. 이 배열을 ComparableTo 메서드의 비교 방식에 따라서 오름차순으로 만들고 싶다. 오름차순이란 작은 수부터 큰 수로 정렬되는 것을 의미한다. 즉 기준이 되는 값(앞의 수)에서  비교대상이 되는 값(뒤의 수)를 뺏을 때 음수값이 나와야 한다. 

때문에 기준이 되는 값 5에서 4를 비교하고, 4에서 3을 비교하고, 3에서 2를 비교하고, 2에서 1를 비교하면 된다.

더 정확히는 5-4, 4-3, 3-2, 2-1 의 값 값이 양수인지 음수인지를 계산하는 것이다. 계산 결과 양수면 자리를 서로 바꿔서 음수 값이 나오게 수를 교환하면서 배열을 만들어 준다.

 

만약 1 2 3 4 5 를 내림차순으로 정렬을 하고 싶다면 앞의 값에서 뒤에 값을 뺐을 때 양수 값이 나와야한다.

즉 1 -2, 2-3, 3-4, 4-5 를 했을 때 양수 값이 나오도록 하는 배열이 오름차순 정렬이 된 상태이기 때문에 자리를 서로 바꿔서 양수 값이 나오게 수를 교환하면서 배열을 생성한다.

 

5. Collection.sort(매개변수 : Comparable인터페이스 구현 클래스) : 기본값은 오름차순

Collection 의 메서드 중에서 가장 많이 사용하는 메서드 중 하나는 sort() 메서드 일 것이다. 이 메서드는 정말 정말 편리한 메서드 중 하나이다. 정확히는 Collection 프레임워크에서 사용하는 데이터 구조 클래스들 중에서도 List 관련된 객체를  매개변수로 넣었을 때 숫자 > 대문자 > 소문자 > 한글순 순서로 && 오름차순으로 정렬해주는 메서드이다.

 

이 메서드가 정말 중요한 것이 단순히 List 관련된 객체를 배열해주는 것 뿐만 아니라 Comparable 인터페이스를 구현한 구현 클래스의 객체를 넘겨줘도 기본값인 오름차순으로 배열해준다는 점이다.

 

사실 지금까지 이렇게 장황하게 Comparable 인터페이스가 어쩌구 구현이 어쩌구 오름차순이 어쩌구 하면서 했던 모든 것들이 이 Collection.sort 메서드와 관련해서 이해하기 위해서이다.

 

자 그럼 다시 생각해보자.
1. Comparable 인터페이스의 구현 클래스에서 구현해줘야하는 메서드는 단 하나이다. ComparableTo 메서드
2. 이 메서드를 사용하면 자기 자신과 메서드의 매개변수로 넘어오는 객체의 값을 비교해준다.
3. 비교해줄 때 값이 크다 작다 같다의 기준은 자기 자신의 값과 매개변수로 넘어오는 객체의 값을 뺐을 때 음수면 작다, 양수면 크다, 0 이면 같은 값이다 라고 인식한다.
4. 오름차순은 앞의 값과 뒤의 값을 뺐을 때 음수 값이 나오며 이 말은 곧 오름차순의 경우 앞의 값과 뒤의 값을 뺐을 때 음수값이 나오면 순서 교환을 하지 않고, 양수값일 때만 순서교환을 한다는 의미이다.
내림차순은 앞의 값에서 뒤의 값을 뺐을 때 내림차순의 경우 양수값이 나오면 순서 교환이 없고 음수값일 때만 순서교환을 한다는 것이다 => 오름차순은 음수면 그대로 양수면 교환, 내림차순은 양수면 그대로 음수면 교환
5. Collection.sort 는 기본값으로 오름차순으로 정렬해주는 메서드이다. 

 

1 ~ 5 까지를 다시 기억하고 아래 문제를 생각해보자. 다 기억하기 싫으면 딱 하나만 기억하자. 

< 오름차순은 음수면 그대로 양수면 교환, 내림차순은 양수면 그대로 음수면 교환 >

 

문제 제시
나는 총 N명의 등급을 정렬하고 싶다. 단 정렬하는 기준은 아래와 같다
1. 등급은 오름차순으로 정렬한다.
2. 등급이 같은 경우 점수는 내림차순으로 정렬한다.
3. 첫 줄에는 총 인원이 N 이 들어오고 2번째 줄 부터 등급과 점수가 주어진다.

 

 

그럼 코드는 아래처럼 만들어진다.

• Comparable 인터페이스를 구현한 클래스는 Point 클래스이다. 해당 클래스는 등급 grade 과 score 를 전역 변수로 갖는다.
• 클래스가 구현한 CompareTo 메서드는 grade 와 socre 를 갖는데 자신의 grade 와 매개변수의 grade 를 비교해서 두 값이 같으면 매개변수로 넘어온 score 에서 자신의 score 를 뺀다.
• 만약 grade가 서로 다른 값인 경우 자신의 grade 에서 매개변수의 grade 를 뺀다.
• 이후 Point가 남긴 list 를 Collection.sort() 를 통해서 정렬한다.

package algorithm;

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

public class Sorting_coordinate {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();

        ArrayList<Point> list = new ArrayList<>();

        for(int i=0; i<n; i++){
            int grade = scan.nextInt();
            int score = scan.nextInt();

            list.add(new Point(grade, score));
        }

        Collections.sort(list);
        for(Point p : list){
            System.out.println(p.x + " " + p.y);
        }
    }
}

// comparable 인터페이스의 구현체
// 이 comparable 인터페이스를 구현한 구현 클래스는 아래의 compareTo 메소드를 통해 객체간 순서를 비교할 수 있다
// 즉 Comparable 인터페이스를 구현한 클래스는 해당 객체들에게 순서가 존재하게 된다.
// 또한 이 인터페이스의 구현체 클래스의 객체는 Collection.sort 를 통해 아주 쉽게 정렬이 가능하다

// sort 매서드의 기본은 오름차순 => 즉 앞에 오는 수에서 뒤에 오는 수를 뺐을 때 음수가 나오면 그대로, 양수가 오면 자리변경
// reverseOrder() 를 사용할 경우 내림차순 => 즉 앞에 오는 수에서 뒤에 오는 수를 뺐을 때 양수가 나오면 그대로, 음수가 나오면 자리변경
class Point implements Comparable<Point> {
    public int grade, score;

    Point(int grade, int score){
        this.grade = grade;
        this.score= score;
    }

    // 객체를 비교해주는 compareTo 메서드 => 이 메서드는 int 를 return 함
    // 대상 객체와 넘어오는 객체를 비교해서 int 양수면 정렬, 0 이면 그대로, 음수면 정렬 의 형태를 취한다
    // 더 자세하게 정리하자면 다음과 같다. 기본은 오름차순 정렬
//     대상 객체 x 와 넘어오는 객체 o 를 비교해서 x - o 가 양수라면 x > o 임을 알 수 있고 이로인해 x-> o 순서가 된다
//     대상 객체 x 와 넘어오는 객체 o 를 비교해서 x - o 가 음수라면 x < o 임을 알 수 있고 이로인해 o->x 순서가 된다
//     최종 정리를 하자면 음수값이 return 되면 오름차순 정렬, 양수값이 return 되면 내림차순 정렬

    // 여기서 중요한 점은 오름차순의 경우 당연하게도 앞에있는 숫자가 뒤에잇는 숫자보다 작다.
    // 때문에 앞에오는 숫자 - 대상 객체, 작은 숫자 - 에서 뒤에 오는 숫자 - 넘어오는 객체, 큰 숫자 - 를 빼서 음수값을 만들어서 오름차순 정렬을 하는 것이다.

    // 반대로 내림차순의 경우 당연하게도 앞에 있는 숫자가 뒤에 있는 숫자보다 크다.
    // 때문에 앞에 오는 숫자 - 대상 객체, 큰 숫자 - 에서 뒤에 오는 숫자 - 넘어오는 객체, 작은 숫자 - 를 빼서 양수값을 넘기면 sort 의 기본은 내림차순 정렬이기 때문에 양수값이 넘어오면
    // 앞의 값이 뒤의 값이 크다고 간주하고 sort 매서드가 내림차순 정렬을 하기위해 앞과 뒤의 숫자를 교환해버리게 된다.
    // 즉 오름차순 정렬로 바뀌어 버리는 것이다.
    // 이를 해결하기 위해서는 두 가지 방법이 있을 수 있다.
    // 1. -(앞의 값 - 뒤의 값)
    // 2. 뒤의 값- 앞의 값


    // 기본 기준은 음수

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

}

사실 자신의 grade 에서 매개변수의 grade 를 빼는 것은 이해가 된다. Collection.sort 의 기준은 오름차순이고 오름차순은 이야기했듯이 앞의 값에서 뒤의 값을 뺐을 때 음수면 순서가 그대로 양수면 앞의 값이 뒤의 값보다 큰 것이니까 순서를 교환해서 자연스럽게 오름차순으로 정렬된다. grade 는 자신의 값에서 매개변수의 값을 뺐을 때 자연스럽게 정렬된다.

 

그런데 여기서 다시 의문이 든다. 왜 매개 변수의 score 에서 자신의 score를 빼는걸까? 정확히는 왜 뒤의 값에서 앞의 값을 빼는걸까? 바로 score 는 내림차순 정렬, 즉 양수값을 return해야하기 때문이다. 

 

우리는 socre 는 오름차순이 아닌 내림차순으로 정렬해야한다. 내림차순의 특징은 앞의 값에서 뒤의 값을 뺐을 때 양수가 나오는 것이다. 동시에!!! 뒤의 값에서 앞의 값을 빼면? 음수가 나온다. 이때!!! 계속 이야기했지만 Collection.sort 의 기본은 음수값이면 그대로 양수값이면 두 수를 교환하는 오름차순이다.

결국 내림차순은 뒤의 값에서 앞값의 값을 빼면 음수가 나오고, 음수가 나온다는 것은 앞의 값과 뒤의 값의 교환이 없다는 것이다. 왜냐고? sort 의 기준은 오름차순이니까. 오름차순은 음수면 수의 교환이 일어나지 않으니까...!!

 

6. 정리

말이 길어지긴 했는데 결국 진짜진짜 최종으로 정리하자면 다음과 같다.

• Comparable interface 를 구현한 구현 클래스는 Collection.sort() 의 매개변수로 들어갈 수 있다. 이때 정렬은 Comparable interface 의 구현 클래스인 ComparableTo 를 기준으로 한다.
• ComparableTo 에서 음수값은 앞의 수가 뒤의 수보다 작다, 양수값은 앞의 수가 뒤의 수보다 크다를 의미한다.
• 오름차순 정렬은 음수값 일 때는 수의 교환이 일어나지 않고, 양수값일 때는 수의 교환이 일어난다. 반대로 내림차순 정렬은 양수값 일때는 수의 교환이 일어나지 않고, 음수값일 때는 수의 교환이 일어난다.
• Collection.sort() 의 기본설정은 오름차순 정렬이다.
• Comparable 인터페이스 말고도 객체를 비교하기 위해 사용되는 Comparator 인터페이스가 있는데 이름에서도 보이다싶이 기능이 아주아주 비슷하다. 단지 Comparable 는 자기 자신과 매개 변수의 대상과 비교라면 Comparator 은 2개의 매개변수를 받고, 두 개를 비교해주는 역할을 한다
  • 사실 이와 관련해서 더 적고 공부해야했으나...여기까지만 이해하는데도 정말 엄청 오래걸려서 일단 패스...

 

 

---

관련해서 볼만한 문제

사실 코드는 위에 적힌 코드 그대로 가져다 써도 무방하다. 

이 문제는 아마 Comparable 인터페이스를 사용할 수 있는가를 보는 문제가 아닐까...도 생각한다.

물론 다른 방법도 있겠지만

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

11650번: 좌표 정렬하기

 

 

---

Reference : 꼭 함께 봐야하는 블로그들 감사합니다

https://cloudstudying.kr/questions/6

Comparable 인터페이스가 무엇인가요? | CloudStudying

https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

 

https://wjheo.tistory.com/entry/Java-%EC%A0%95%EB%A0%AC%EB%B0%A9%EB%B2%95-Collectionssort

Java 정렬방법 Collections.sort()