이번에는 지난 글에서 다뤘던 Comparable과 Comparator를 활용하여 정렬해보는 시간을 가져보겠습니다.
지난 글을 전부 이해하셨다면 이번 글은 금방 이해하실 수 있을겁니다.
두 인터페이스를 간단히 정리해보면 이렇습니다.
Comparable - compareTo(T o) 추상 메서드를 가진 인터페이스
(자신과 객체 o를 비교)
Comparator - compare(T o1, T o2) 추상 메서드를 가진 인터페이스
(o1 객체와 o2 객체를 비교)
그리고 여기서 한가지 알고 가셔야 할 점이 있습니다.
대부분 프로그래밍에서의 정렬은 오름차순이 디폴드입니다.
오름차순의 특징을 한번 볼까요?
{1, 2, 3, 4, 5}
보시면, 앞의 값이 뒤에 값보다 작습니다.
그러면 앞의 값 - 뒷 값 을 하면 음수가 나오겠죠.
음수?? 어디서 들어보시지 않았나요?
맞습니다. compareTo나 compare 메서드에서 비교연산을 할 때, 값이 크거나 작거나 같으면, 1, 0, -1
즉, 양수, 0, 음수를 반환하죠.
이를 이용하는 것입니다.
만약 비교했을 때, 음수이면 이미 앞의 값보다 뒤쪽 값이 더 크므로 오름차순이 되어있습니다.
반대로 양수라면, 앞쪽 값이 뒤쪽 값보다 큰 경우겠죠. (ex) {3, 1}
그러면 이 두개의 값을 바꿔주면 됩니다. 오름차순이 되겠죠.
지금까지는 고정으로 1, 0, -1의 값을 반환해줬죠. 그렇게 오름차순처럼 되었습니다.
그러면 내림차순은 어떻게 해야할까요?
현재 반환하는 값을 전부 반대로만 반환해주면 됩니다.
기존에는 그냥 this.age > o.age 라면 return 1;
this.age < o.age 이면 return -1;
같으면 0을 해줬다면
this.age > o.age 는 return -1;
this.age < o.age 는 return 1;
같으면 0 이렇게 말이죠.
일단 이렇게 알아두고 밑에 더 진행하면서 보겠습니다.
1. Comparable를 이용한 정렬
먼저 지난번에 다뤘던 Student 객체에서 이름도 인스턴스 변수로 받아보겠습니다.
class Student implements Comparable<Student> {
String name;
int age;
int classNumber;
Student(String name, int age, int classNumber) {
this.name = name;
this.age = age;
this.classNumber = classNumber;
}
public int compareTo(Student o) {
return (this.age > o.age) ? 1 : (this.age < o.age) ? -1 : 0;
}
public String toString() {
return "이름 : " + this.name + ", " + "나이 : " + this.age + ", " + "반 : " + this.classNumber;
}
}
여담으로 Comparable 인스턴스로 인해 상속받은 compareTo 메서드 안에는 return 값이 좀 복잡해 보이지만 이는 삼항 연산자입니다.
(비교연산) ? true : false;
괄호 안 비교연산이 참이면 true 자리의 값을, 거짓이면 false 자리의 값을 반환합니다.
그러면 이건 결과가 뭘까요?
(10 > 20) ? 100 : 200;
10 > 20은 거짓이죠. 그러면 거짓 자리인 200을 반환합니다.
그럼 compareTo 메서드의 삼항 연산자를 한번 보죠
(this.age > o.age) ? 1 : (this.age < o.age) ? -1 : 0;
차근차근 보겠습니다.
1. (this.age > o.age) 가 참이면 true 자리인 1을
2. (this.age > o.age) 가 거짓이면 false 자리인 (this.age < o.age)를 반환하는데
3. (this.age > o.age) 가 거짓일 때의 (this.age < o.age)가 참이면 -1을
4. (this.age > o.age) 가 거짓일 때의 (this.age < o.age) 가 거짓이면 0을 반환합니다.
즉 if_else if_ else 문 인거죠.
잠깐 삼항연산자에 대한 간단한 소개였습니다.
다시 본론으로 돌아가서...
마지막에 toString 메서드가 있는데, 이는 제일 최상위 클래스인 object 클래스의 toString을 오버라이딩 해서 객체 값을 재정의 한 것입니다. 간단히 보면, 객체 이름이 저렇게 호칭만 바꼈다고 보시면 좀 편할까요?
저는 그래서 이름 : 무엇, 나이 : 무엇, 반 : 무엇 으로 출력되게끔 만든겁니다.
그러면 이제 4개의 Student 인스턴스를 만들어서 래퍼런스 배열변수에 저장해 봅시다.
public class StudentCompareTest {
public static void main(String[] args) {
Student [] x;
x = new Student[] {
new Student("영민", 18, 1),
new Student("상원", 20, 3),
new Student("하윤", 11, 4),
new Student("명수", 21, 2)
};
}
}
현재 Student 클래스 타입의 x 래퍼런스 변수는 배열입니다.
따라서 x 래퍼런스 값은 Student 클래스 타입의 값만 받을 수 있겠죠.
현재는 "영민", "상원", "하윤", "명수"의 대한 정보가 들어갑니다. 각각 18살 20살 11살 21살이군요.
우리가 정렬을 사용할 때 가장 많이 쓰는 메서드가 있죠.
네 바로 Arrays.sort() 메서드 입니다. 바로 적용해볼게요
class Student implements Comparable<Student> {
String name;
int age;
int classNumber;
Student(String name, int age, int classNumber) {
this.name = name;
this.age = age;
this.classNumber = classNumber;
}
public int compareTo(Student o) {
return (this.age > o.age) ? 1 : (this.age < o.age) ? -1 : 0;
}
public String toString() {
return "이름 : " + this.name + ", " + "나이 : " + this.age + ", " + "반 : " + this.classNumber;
}
}
public class StudentCompareTest {
public static void main(String[] args) {
Student [] x;
x = new Student[] {
new Student("영민", 18, 1),
new Student("상원", 20, 3),
new Student("하윤", 11, 4),
new Student("명수", 21, 2)
};
Arrays.sort(x);
for(int i = 0; i < 4; i++) {
System.out.println(x[i]);
}
}
}
이름 : 하윤, 나이 : 11, 반 : 4
이름 : 영민, 나이 : 18, 반 : 1
이름 : 상원, 나이 : 20, 반 : 3
이름 : 명수, 나이 : 21, 반 : 2
위 코드를 실행하면 위와같은 결과가 나옵니다. 나이순으로 잘 정렬이 되었습니다.
그러면 내림차순은 어떻게 한다고 했죠?
값을 반대로만 반환해주면 된다고 했습니다.
바로 적용해볼게요.
class Student implements Comparable<Student> {
String name;
int age;
int classNumber;
Student(String name, int age, int classNumber) {
this.name = name;
this.age = age;
this.classNumber = classNumber;
}
public int compareTo(Student o) {
return (this.age > o.age) ? -1 : (this.age < o.age) ? 1 : 0; // 기존 1, -1, 0 에서 -1, 1, 0으로 반대로 바꿈
}
public String toString() {
return "이름 : " + this.name + ", " + "나이 : " + this.age + ", " + "반 : " + this.classNumber;
}
}
이름 : 명수, 나이 : 21, 반 : 2
이름 : 상원, 나이 : 20, 반 : 3
이름 : 영민, 나이 : 18, 반 : 1
이름 : 하윤, 나이 : 11, 반 : 4
메인 메서드는 같습니다. 결과를 보면 내림차순으로 출력되는 것을 볼 수 있습니다.
2. Comparator를 이용한 정렬
그러면 이번에는 Comparator를 이용해서 정렬을 시도해 보겠습니다.
위 학생들의 정보는 그대로 가져가고 인터페이스와 메서드만 달리 해보겠습니다.
class Student {
String name;
int age;
int classNumber;
Student(String name, int age, int classNumber) {
this.name = name;
this.age = age;
this.classNumber = classNumber;
}
public String toString() {
return "이름 : " + this.name + ", " + "나이 : " + this.age + ", " + "반 : " + this.classNumber;
}
}
class StudentComparator implements Comparator<Student> {
public int compare(Student s1, Student s2) {
return (s1.age > s2.age) ? 1 : (s1.age < s2.age) ? -1 : 0;
}
}
public class StudentCompareTest {
public static void main(String[] args) {
StudentComparator comp = new StudentComparator();
Student [] x;
x = new Student[] {
new Student("영민", 18, 1),
new Student("상원", 20, 3),
new Student("하윤", 11, 4),
new Student("명수", 21, 2)
};
Arrays.sort(x, comp);
for(int i = 0; i < 4; i++) {
System.out.println(x[i]);
}
}
}
뭔가 달라졌죠? 결과는 같습니다.
Student 클래스 안에 compare 메서드가 없어지고 StudentComparator 라는 클래스가 Comparator 인터페이스를 대신 구현해서 compare 메서드를 재정의 했습니다.
그리고 main 메서드에서 StudentComparator라는 클래스를 comp라는 래퍼런스 변수에다 new 라는 키워드를 통해 인스턴스를 생성했죠.
이렇게 따로 클래스를 만들어서 비교만 해주는 기능을 가진 클래스를 만든것은 이유가 있습니다.
바로 Arrays.sort()메서드 때문인데요.
잠깐 Arrays.sort() 메서드를 보고 가실까요?
뭐... 뭐라는지 잘 모르겠지만, 매개변수가 우리가 생각한 것과는 조금 차이가 있어보입니다.
단순히 배열만 받을 줄 알았는데 Comparator 를 c라는 매개변수로 받기도 합니다???
이게 바로 StudentComparator 라는 클래스를 따로 만든 이유입니다. Arrays.sort 메서드는 Comparator에 대한 내용도 받아서 정렬을 해주기 때문이죠.
즉, sort메서드는 오버로딩 되어있는 것이죠.
실제로 api 문서를 보면 배열만 받는 sort 메서드가 있습니다.
3. 정리해 봅시다.
Comparable을 이용하여 정렬을 시도하려고 하면, Comparator의 값은 없기 때문에, Arrays.sort(object[] a) 메서드를 호출하면서 Comparable을 구현한 클래스의 compareTo 메서드를 사용해서 정렬을 합니다.
Comparator을 이용하여 정렬을 시도하려고 하면, Comparator 를 구현한 클래스의 Compare() 메서드를 이용해서 정렬을 해줍니다. 즉, Arrays.sort(T[] a, Comparator<? super T> c) 메서드를 호출해서 정렬을 해주는 것이지요.
4. binarySearch 메서드를 이용한 응용
Comparator의 compare메서드만 정의되어있는 클래스를 만들어주면서 '이 방식대로 연산해줘' 라고 알려줄 수 있게 되었습니다.
이를 이용해서 binarySearch 메서드에 적용할 수 있습니다.
binarySearch는 이진 탐색 알고리즘이죠. 지난번에 PL, PC, PR을 변수로 두면서 직접 구현했었는데, 사실 이 메서드 하나면 바로 해당값의 인덱스 번호를 출력해 줍니다.
public class BinarySearchTest {
public static void main(String[] args) {
int[] numArr = new int[] {10, 20, 30, 40, 50, 60, 70, 80, 90};
int searchNum;
Scanner sc = new Scanner(System.in);
System.out.print("검색할 숫자를 입력하세요: ");
searchNum = sc.nextInt();
System.out.println("Arrays.binarySearch 사용 : " + Arrays.binarySearch(numArr, searchNum));
}
}검색할 숫자를 입력하세요: 20
Arrays.binarySearch 사용 : 1
심지어 이 메서드는 값이 없을 경우, 그 값이 어떤 위치에 들어가야 하는지도 알려줍니다.
만약 25를 입력하면 numArr 변수에 3번째에 들어가야한다면서 -3을 반환합니다.
검색할 숫자를 입력하세요: 25
Arrays.binarySearch 사용 : -3
이런 binarySearch 메서드에도 객체, 찾으려는 값(key), Comparator 를 받는 메서드가 있습니다.
이를 이용해서 바로 예제를 보겠습니다.
import java.util.Comparator;
public class HeightOrderComparator implements Comparator<PhysicalData> {
public int compare(PhysicalData d1, PhysicalData d2) {
return (d1.height > d2.height) ? 1 : (d1.height < d2.height) ? -1 : 0;
}
}public class PhysicalDataExam {
public static void main(String[] args) {
final Comparator<PhysicalData> HEIGHT_ORDER = new HeightOrderComparator();
Scanner stdIn = new Scanner(System.in);
PhysicalData[] x = { // 키의 오름차순으로 정렬
new PhysicalData("강민하", 162, 0.3),
new PhysicalData("이수연", 168, 0.4),
new PhysicalData("황지안", 169, 0.8),
new PhysicalData("유서범", 171, 1.5),
new PhysicalData("김찬우", 173, 0.7),
new PhysicalData("장경오", 174, 1.2),
new PhysicalData("박준서", 175, 2.0),
};
System.out.print("키가 몇 cm인 사람을 찾고 있나요?: ");
int height = stdIn.nextInt();
stdIn.close();// 킷값을 읽어 들임
int idx = Arrays.binarySearch(x, new PhysicalData(height), HEIGHT_ORDER);
if (idx < 0)
System.out.println("그 값의 요소가 없습니다.");
else {
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[idx]);
}
}
}(해당 예제는 'Do it! 자료구조와 함께 배우는 알고리즘 입문' 책의 예제입니다.)
마지막 if문 위의 int idx를 보시면 됩니다.
binarySearch 메서드를 불러와서 학생 데이터들이 담긴 래퍼런스 배열 x와, 찾고자하는 키 값을 PhysicalData 클래스의 인스턴스 height로 두고, 이진 탐색이기 때문에 정렬 방법은 HEIGHT_ORDER 클래스로 두었습니다.
그러면 HEIGHT_ORDER 클래스로 인해 학생 정보가 담긴 래퍼런스 x 배열은 정렬이 되겠죠.
그 후, 정한 키값을 찾아서 그 키값이 어떤 위치에 있는지를 반환해줍니다.
만약 찾으려는 키 값이 없다면 '이 위치에 들어가야 돼' 라면서 음수값을 반환하겠죠. 그러면 "그 값의 요소가 없습니다"를 출력합니다.
이런식으로 쓰이기도 한다는걸 알려드리기 위해 한번 가져와봤습니다. 저 코드가 이해가 안되어도 우선 Comparable 과 Comparator를 이용해서 정렬이 가능하다는것을 이해하셨다면 성공입니다.