자바로 정렬 알고리즘을 풀다가 막혀서 해설을 보다보면 항상 나오는게 Comparable과 Comparator를 이용한 풀이이다. 보다 잘 이해하고 익숙해지기 위해서 정리를 하고자 한다.
객체 정렬에 필요한 메서드(정렬기준 제공)를 정의한 인터페이스
즉 인터페이스 내에 선언된 메소드를 구현해야하는데,
실질적으로 우리가 구현해야할 메소드는 각각 다음과 같다.
Comparable: int compareTo(T o)
Comparator: int compare(T o1, T o2)
Comparable과 Comparator는 객체를 비교할 수 있게 해주며,
compareTo와 compare는 두 객체의 비교결과를 반환하도록 작성하면 된다.
compareTo는 주어진 객체 o를 자기자신(this)와 비교하기 때문에 매개 변수가 한 개인 것이고, compare는 두 매개변수 객체를 비교하기에 두 개인 것이다.
+) Comparable은 lang패키지에 있기에 import가 필요없지만, Comparator는 util패키지를 import해야한다.
비교하고자 하는 클래스에 implements Comparable<T>
를 해준 후 compareTo
메소드를 @Override해주면 된다.
이때 반환값은 오름차순 시에 자기자신을 기준으로 비교값보다 작으면 음수, 크면 양수, 같으면 0을 반환한다.
compare()메소드가 Comparable의 compareTo()메소드와 다른 점은 그저 객체 하나가 더 추가됐다는 것이고, 첫 번째 매개변수를 기준으로 두 번째 매개변수와 비교를 진행한다. 즉 자기자신(this)는 비교에 영향을 주지 않는다.
Object.compare(T o1, T o2)에서 Object는 영향을 주지 않는 것이다.
이와 같은 문제에서 우리는 Comparator 비교 기능만 따로 두고 싶은 생각이 든다. 이를 해결하기 위해 anonymous class를 사용한다.
+) anonymous class는 상속할 대상이 있어야 한다.
Java에서의 정렬은 기본적으로 오름차순으로 정렬된다.
즉 compare()나 compareTo()의 반환값이 음수이면 두 원소의 위치를 바꾸지 않고, 양수이면 위치를 바꾸는 것이다.
자바에서 sort는
Comparable에 의한 정렬인
static void sort(Object[] a)
의 형태와 Comparator에 의한 정렬인static void sort(Object[]a, Comparator c)
의 형태로 동작한다.
그저 Arrays.sort(Object o1)
와 같이 사용을 하려면 o1 객체가 Comparable을 구현한 클래스여야 하는 것이다. => 내부적으로 compareTo를 사용한다.
그렇다면 Comparator는 어떻게 사용할까?
그렇다. Arrays.sort(Object o1, Comparator c)
이다.
이때 Comparator를 직접 생성할수도, 익명 객체로써 생성할 수 있다.
Arrays.sort(Object o1, new Comparator<T>(){@Override compare~~~}
이런 식으로 compare메소드를 안에 구현하면 정렬이 수행된다.
자바가 정렬을 내부적으로 이런식으로 수행한다고 생각하면 된다.
static void sort(Object[] objArr, Comparator C){
for(int i=0; i<objArr.length-1; i++){
for(int j=0; j<objArr.length-1-i; j++){
Object temp = null;
if(c.compare(objArr[j], objArr[j+1])>0){
tmp=objArr[j];
objArr[j]=objArr[j+1];
objArr[j+1]=tmp;
}
}
}
}
우리는 비교 기준이 되는 Comparator를 구현만 해서 가져다 넣으면 되는 것이다!!
이를 활용하는 문제를 풀어보면서 개념을 더 확실하게 익힐 수 있다.
https://programmers.co.kr/learn/courses/30/lessons/42746
import java.util.*;
class Solution {
public String solution(int[] numbers) {
String answer = "";
StringBuilder sb = new StringBuilder();
String[] strings = new String[numbers.length];
int len = numbers.length;
for(int i=0; i<len; i++){
strings[i] = Integer.toString(numbers[i]);
}
Arrays.sort(strings, new Comparator<String>(){
@Override
public int compare(String a, String b){
return (b+a).compareTo(a+b);
//오름차순 정렬 (a+b).compareTo(b+a);
}
});
for(int i=0; i<len; i++){
sb.append(strings[i]);
}
answer = sb.toString();
if(strings[0].equals("0")) answer="0";
return answer;
}
}
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparator<String>
을 사용할 때 기본 정렬 시 compareTo를 사용할 수 있다.글 작성시 참고한 글과 영상입니다.
https://st-lab.tistory.com/243 (Comparable과 Comparator의 이해 - ST_)
https://www.youtube.com/watch?v=EW3Mub24wYg (자바의 정석 - 기초편, Comparator와 Comparable - 남궁성의 정석코딩)
https://ivory-room.tistory.com/43 (프로그래머스 Lv2 가장 큰 수 java - 개발로 자기개발)
틀린 개념이나 의문점이 있을 시 편하게 댓글 달아주시면 감사하겠습니다 :)