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

풀이방법

이 문제는 어제 풀어보았던 단어 정렬 문제와 비슷한 유형입니다. 바로 Comparator 혹은 Comparable을 구현해서 정렬하는 문제입니다. 그럼 여기서 의문이 생길 수 있습니다.

그냥 sort를 사용해서 정렬을 하면 되는데, 왜 저런 것을 사용하는거지??

sort는 하나의 값을 기준으로 정렬할 때 사용할 수 있지만, 객체를 정렬할 때는 사용하지 못하기 때문입니다. 즉 객체의 어떤 속성(값)을 기준으로 정렬할 지 모호하기 때문에 Comparable 혹은 Comparator를 구현해서 원하는 정렬을 진행해야 합니다. 사용법만 안다면 간단하게 구현할 수 있습니다.

  1. Comparable 구현
    Comparable은 객체가 될 클래스가 Comparable을 구현함으로써 사용 가능합니다. compareTo라는 함수를 오버라이드 해서 클래스의 객체인 Coordinates와 this의 x,y 값을 비교해서 값을 리턴하게 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.io.*;
import java.util.*;

public class BOJ11650 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(bf.readLine());
        List<Coordinates> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list.add(new Coordinates(x, y));
        }

        Collections.sort(list);

        for (int i = 0; i < list.size(); i++)
            bw.write(list.get(i).x + " " + list.get(i).y + "\n");

        bw.flush();
        bw.close();
        bf.close();
    }
}

class Coordinates implements Comparable<Coordinates> {
    int x;
    int y;

    public Coordinates(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Coordinates o) {
        // 오름 차순일 경우
        // this를 기준으로 함
        // this가 크면 1, this가 작으면 -1 : 오름차순 정렬!
        // 여기서 비교하는 값은 o라는 객체가 됨.
        if (this.x > o.x) {
            return 1;
        } else if (o.x == this.x) {
            if (this.y > o.y) {
                return 1;
            } else {
                return -1;
            }
        } else if (this.x < o.x) {
            return -1;
        } else {
            return 0;
        }
    }
}
  1. Comparator 구현
    Comparator를 구현하면 compare()라는 메소드를 오버라이드 합니다. 이 함수는 매개 변수로 두 개의 객체가 들어있어서 두 개의 객체를 비교하여 리턴하는 값에 따라서 정렬된 값을 알 수 있습니다. 두 객체를 비교해서 음수, 0, 양수를 반환하도록 합니다. Comparator를 구현하면 기본 정렬 외에도 다른 기준으로 정렬하고자 할 때 사용할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package language;

import java.io.*;
import java.util.*;

public class BOJ11650 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(bf.readLine());
        List<Coordinates> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list.add(new Coordinates(x, y));
        }


        // Comparator를 이용한 방법
        list.sort(new Comparator<Coordinates>() {
            @Override
            public int compare(Coordinates o1, Coordinates o2) {
                // o1을 기준으로 잡는다.
                // o2가 비교하는 객체가 된다.
                // 오름 차순!
            
                if (o1.x == o2.x) {
                    if (o1.y > o2.y) {
                        return 1;
                    } else {
                        return -1;
                    }
                }else if(o1.x>o2.x){
                    return 1;
                }else if(o1.x<o2.x){
                    return -1;
                }else {
                    return 0;
                }
            }
        });

        Collections.sort(list);

        for (int i = 0; i < list.size(); i++)
            bw.write(list.get(i).x + " " + list.get(i).y + "\n");

        bw.flush();
        bw.close();
        bf.close();
    }
}

class Coordinates {
    int x;
    int y;

    public Coordinates(int x, int y) {
        this.x = x;
        this.y = y;
    }

}

참고 : Collection Framework 중 Comparable, Comparator에 관한 내용