[JAVA] Comparator 인터페이스의 이해

 

알고리즘을 공부하고, 백준에서 여러 문제들을 풀어보면서 Comparator를 통한 정렬을 많이 사용한다.

 

잘 알지도 못 하면서 그냥 쓰기만 하니 찝찝해서 이번 기회에 Comparator 인터페이스를 본격적으로 분해해 보려고 한다.

 

Comparator 인터페이스 구성

https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#method.summary

Comparator (Java Platform SE 8 )

 

우선 Comparator 인터페이스에는 다음과 같이 굉장히 많은 메소드 들이 존재한다.

 

하지만 다 default method고 우리가 필수적으로 구현해야할 추상 메소드는 compare 하나밖에 없다.

    int compare(T o1, T o2);

    /**
     * Indicates whether some other object is "equal to"
     * this comparator.  This method must obey the general contract of
     * {@link Object#equals(Object)}.  Additionally, this method can
     * return {@code true} <i>only</i> if the specified object is also
     * a comparator and it imposes the same ordering as this
     * comparator.  Thus, {@code comp1.equals(comp2)} implies that
     * {@link Integer#signum signum}{@code (comp1.compare(o1,
     * o2))==signum(comp2.compare(o1, o2))} for every object reference
     * {@code o1} and {@code o2}.<p>
     *
     * Note that it is <i>always</i> safe <i>not</i> to override
     * {@code Object.equals(Object)}.  However, overriding this method may,
     * in some cases, improve performance by allowing programs to determine
     * that two distinct comparators impose the same order.
     *
     * @param   obj   the reference object with which to compare.
     * @return  {@code true} only if the specified object is also
     *          a comparator and it imposes the same ordering as this
     *          comparator.
     * @see Object#equals(Object)
     * @see Object#hashCode()
     */

 

Comparator의 용도

Comparator는 말 그대로 비교를 위한 인터페이스다.

 

정확히 말하자면 비교의 기준을 설정하기 위한 인터페이스다.

무슨 말인지 이해가 잘 가지 않을 것이다.

 

단순 primitive 타입의 실수 변수(byte, int, double,long ,,)일 경우 부등호만 있다면 쉽게 비교를 할 수 있다.

 

그러나 문자를 비교할 때는 어떻게 비교할 것인가?

 

클래스, 객체를 비교할 때는 어떻게 비교할 것인가?

 

이것에 대한 기준을 세워주는 것이 Comparator이다.

 

실제 사용 예시를 한 번 보겠다.

 

class Member implements Comparable<Member> {
 
	int age;			
	String name;	
	
	Member(int age, String name) {
		this.age = age;
		this.name = name;
	}
	
	@Override
	public int compare(int o1, int o2) {
    
		if(o1.age > o2.age) {
			return 1;
		}
        
		else if(o1.age == o2.age) {
			return 0;
		}
        
		else {
			return -1;
		}
	}
}

 

우선 compare의 반환형은 정수다. 즉 두 값을 비교해서 정수를 반환해줘야 한다는 것이다.

 

위의 예시를 살펴보자. 

 

o1의 나이와 o2의 나이를 비교해서 o1이 더 크다면 1을 반환하고

o2가 더 크다면 -1을 반환한다.

 

이렇게 코드를 짜서

Member m1 = new Member(20, "홍길동");
Member m2 = new Member(19, "김아무개");
Member m3 = new Member(25, "동방삭");

int a = m1.compare(m1,m2);

a = ??

 

실행을 시켜보면 a엔 1이 담겨있는 것을 확인할 수 있다.

 

자바에서는 이 반환값을 기준으로 정렬을 시킨다.

 

자바의 정렬 기준

자바에서는 기본적으로 '오름차순'을 기준으로 정렬을 시킨다.

 

20,19,25가 있다면,

19,20,25로 정렬을 시킨다는 것이다.

 

그렇다면 m1과 m2를 기준으로 다시 생각해보자

 

20과 19의 compare 값은 1이 반환 됐다.

 

1이 반환 됐다는 의미는 m1이 m2 보다 더 크다는 의미다.

 

그렇다면 오름차순으로 정렬 시키기 위해선 m1과 m2의 위치를 바꿔줘야한다.

 

우리는 여기서 정렬의 기준을 알 수 있다.

 

바로 compare의 반환값이

반환값 > 0 이라면 m1과 m2의 위치를 교환한다.

 

반대로

반환값 < 0 이라면 m1과 m2의 위치를 교환하지 않는다.

 

실제로 자바에 구현된 sort 메소드가 compare의 값을 기준으로 원소를 교환하는 것을 확인할 수 있다.

 

    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low, int high, int off,
                                  Comparator c) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

자바에 구현된 merge sort의 일부분이다. 이를 확인하면 compare 값을 이용해 swap을 진행하는 것을 볼 수 있다.

 

그렇다면 우리는 저 기준을 이용해서 sort를 내림차순으로 이용할 수도 있다.

 

쉽게 생각해보자.

 

반환값 > 0, 일 때 원소를 교환하고

반환값 < 0, 일 때 교환하지 않는다.

 

 반환값을 다시 한 번 살펴보겠다.

 

	@Override
	public int compare(int o1, int o2) {
    
		if(o1.age > o2.age) {
			return 1;
		}
        
		else if(o1.age == o2.age) {
			return 0;
		}
        
		else {
			return -1;
		}
	}

 

위의 반환식을 간단하게 정리하면 다음과 같이 나타낼 수 있다.

 

	@Override
	public int compare(int o1, int o2) {
    
		return o1-o2;
	}

 

자 그럼 이 반환식을 이용해 내림차순을 만드려면 어떻게 해야할까 답은 간단하다.

 

	@Override
	public int compare(int o1, int o2) {
    
		return o2-o1;
	}

 

위와 같이 바꿔주면 된다.

 

이렇게 된다면

 

o2가 o1 보다 클 때, 두 원소를 교환하고

o2가 o1보다 작을 때, 두 원소를 교환하지 않는다.

 

뭔가 좀 복잡해졌지만 

 

선행 원소 즉 o1은 값이 작다고 가정하고, 후행 원소 o2는 값이 크다고 가정하면 이해하기 훨씬 수월할 것이다.

 

주의할 점

덧셈과 뺄셈 과정에서 자료형의 범위를 넘어버리는 경우엔 결과값이 예상했던 것의 반대로 나타나게 된다.

 

이게 무슨말이냐 하면

 

int형은 -2^31 ~ 2^31 -1 의 범위를 가지고 있다.

 

즉, -2,147,483,648 ~ 2,147,483,647의 범위를 가지고 있는 것이다.

 

만약 해당 범위를 벗어나게 된다면, -2,147,483,648 -1 = 2,147,483,647로

int 자료형의 최댓값으로 바뀌게 된다.

 

이러한 점을 고려했을 때 o1이 -2,147,483,648이고 o2가 1이라면 우리가 예상했던 것과 반대의

결과가 나타나게 되는 것이다.

o1 - o2 = + 즉, 양수가 반환 되기에 o1과 o2의 위치가 바뀌게 되고

오름차순이 아닌 내림차순으로 정렬되게 된다,,,

 

이렇듯 자료형의 범위를 벗어나지 않도록 주의하여 코드를 작성하면 되겠다.