Comparator와 Comparable 정리

백준 11650번을 풀다가 Comparator를 사용한 김에 개념 정리를 하려고 한다.

정말 간단한 문제니까 Comparator 재정의하는 연습용으로 괜찮은듯 ㅎ.ㅎ

 

🔻 문제 및 풀이

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

11650번: 좌표 정렬하기

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

 

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

 

---

코드

public class Main {
    public static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(bf.readLine());
        int[][] arr = new int[n][2];
        
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a1, int[] a2) {
                if(a1[0] == a2[0]) {
                    return a1[1] - a2[1];
                } else {
                    return a1[0] - a2[0];
                }
            }
        });
        
        for(int i=0;i<n;i++) {
            sb.append(arr[i][0])
                .append(" ")
                .append(arr[i][1])
                .append("\n");
        }
        bw.write(sb.toString()+"\n");
        
        bf.close();
        bw.close();
    }
}

 

👩‍💻 배열의 정렬

• 오름차순의 경우 Arrays.sort() 사용
• 내림차순의 경우 Collections.reverseOrder()와 함께 사용
  -> Arrays.sort(배열, Collections.reverseOrder())

 

💡 Comparator

정렬 조건을 마음대로 변경하고 싶다면 Comparator의 compare 메소드를 오버라이드 해주면 된다.

Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] a1, int[] a2) {
        if(a1[0] == a2[0]) {
            return a1[1] - a2[1];
        } else {
            return a1[0] - a2[0];
        }
    }
});

compare 메소드에 파라미터 A, B가 있다고 가정해보자.

return 값이 음수라면 B의 우선순위가 더 높고,

return 값이 양수라면 A의 우선순위가 더 높다고 이해한다.

(return 0인 경우에는 A와 B의 우선순위가 같다.)

 

예제의 경우에는 값1 - 값2으로 반환했지만 정수라서 가능한 예시이다.

return 값이 반드시 int형이어야 하므로 파라미터가 String 형이라면 String.compareTo() 메소드를 이용하자.

 

 

🔻 추가 예제: Map을 값 기준으로 정렬하기

Map을 값 기준으로 정렬하기 위해서는 Map 클래스의 Entry를 이용한다.

Map은 키-밸류 쌍으로 이루어진 데이터가 모여있는데 Entry는 키-밸류의 한 데이터를 의미한다.

 

Map의 Entry들을 List에 담아주고,

List의 정렬 기준을 Comparator를 통해 변경할 것이다.

// Map<Integer, Integer> map에 데이터가 존재한다는 가정 하에 진행
List<Map.Entry<Integer,Integer>> mapList = new ArrayList<>(map.entrySet());

Collections.sort(mapList, new Comparator<Map.Entry<Integer,Integer>>() {
    @Override
    public int compare(Map.Entry<Integer,Integer> a1,Map.Entry<Integer,Integer> a2) {
        return a1.getValue() - a2.getValue();
    }
});

 

💡 Comparable

: Comparator처럼 오버라이드해 정렬 기준으로 변경할 수 있는 인터페이스

class Student implements Comparable<Student> {
    int num;
    String name;
    int score;
		
    public Student (int num, String name, int score) {
        this.num = num;
        this.name = name;
        this.score = score;
    }
		
    @Override
    public int compareTo(Student student) {
        return this.num - student.num;
    }
}

위와 같이 implements Comparable<T>를 하면 재정의한 메소드를 이용해 정렬된다.

Student[] arr = new Student[3];
// arr에 값 추가
Arrays.sort(arr);

List<Student> list = new ArrayList<>();
// list에 값 추가
Collections.sort(list);

 

🤔❓ Comparator와 Comparable의 차이

	Comparator	Comparable
메소드	compare()	compareTo()
정렬 대상	파라미터로 들어오는 두 객체	자기 자신과 파라미터로 들어오는 객체
사용 기준	기존의 정렬 기준과 다른 기준으로 정렬하고 싶은 경우	특정 클래스의 기본 정렬 기준을 설정하고 싶은 경우

 

🔻 더 많은 설명

• Comparator: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html
• Comparable: https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html