좌표 정렬 구현하기 (Comparable)

좌표 정렬

 

설명

N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.

정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.

입력

첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.

두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.

출력

N개의 좌표를 정렬하여 출력하세요.

예시 입력 1 

5
2 7
1 3
1 2
2 5
3 6

예시 출력 1

1 2
1 3
2 5
2 7
3 6

 

Java 의 Collections.sort 의 동작원리

Java 의 Collections sort 는 compareTo 라는 method 를 활용해 내림 차순 및 오름 차순을 구분합니다.

 

compareTo method 의 리턴값이 음수면 오름 차순 양수면 내림 차순 입니다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class CoordinateAlignment {

    public static class Coord implements Comparable<Coord> {

        public int x, y;

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

        @Override
        public int compareTo(Coord coord) {
            if (this.x == coord.x) {
                // 오름 차순으로 정렬 하고 싶으면 음수가 return 되어야 하고
                // 내림 차순으로 정렬 하고 싶으면 양수가 return 되어야 한다.
                return this.y - coord.y;
            }
            return this.x - coord.x;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Coord> coords = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            coords.add(new Coord(x, y));
        }

        // Collection sort 의 정렬 기준은 compareTo 인데 우리가 Overriding 한 method 로 바꿔 실행 시켜줌
        Collections.sort(coords);

        for (Coord coord : coords) {
            System.out.printf("%d %d\n", coord.x, coord.y);
        }
    }
}

 

this.x (자기 자신) 과 coord.x 파라미터 로 입력받은 값을 비교하여 오름 차순으로 return 하고

x 값이 같을 경우 y 의 오름 차순으로 return 합니다.