백준 11650번: 좌표 정렬하기

2차원 평면 위의 N개의 점을 정렬하는 문제입니다. 정렬 기준이 x좌표, y좌표 순으로 두 가지이므로, 다중 조건 정렬을 어떻게 구현하는지가 핵심입니다. Java에서는 Comparable 인터페이스를 활용하여 객체의 정렬 기준을 직접 정의할 수 있습니다.

---

✅ 문제 개요

항목	내용
문제 번호	11650번 - 좌표 정렬하기
난이도	실버 5
핵심 알고리즘	정렬, Comparable 인터페이스

---

✅ 문제 설명 요약

• 입력:
  1. 첫째 줄: 점의 개수 N (1 ≤ N ≤ 100,000)
  2. 이후 N개의 줄: 각 점의 x, y 좌표가 공백으로 구분되어 주어짐
• 출력: 정렬된 점의 좌표를 x y 형식으로 한 줄에 하나씩 출력
• 정렬 규칙:
  1. (1차 기준) x좌표가 증가하는 순서로 정렬한다.
  2. (2차 기준) x좌표가 같으면, y좌표가 증가하는 순서로 정렬한다.

---

✅ 풀이 전략

이 문제는 단순한 숫자 정렬이 아닌, (x, y)라는 복합 데이터를 정해진 우선순위에 따라 정렬해야 합니다. 이럴 때는 좌표 데이터를 담을 별도의 클래스를 만들고, 그 클래스에 정렬 기준을 직접 명시해주는 것이 가장 좋은 방법입니다.

1️⃣ 데이터 구조 선택: 좌표 클래스 만들기

• x와 y 좌표를 하나의 단위로 묶어서 다루기 위해, int x와 int y를 멤버 변수로 갖는 Point 클래스를 만듭니다.
• 이렇게 객체로 관리하면 데이터를 다루기가 훨씬 수월하고 코드가 깔끔해집니다.

2️⃣ 비교 기준 정의: Comparable 인터페이스

• Java의 표준 정렬 기능(Arrays.sort())이 우리가 만든 Point 객체를 어떻게 비교해야 할지 알 수 있도록, Comparable 인터페이스를 구현해야 합니다.
• Comparable<Point>를 구현하고, compareTo() 메소드를 오버라이드(재정의)하여 정렬 규칙을 상세히 알려줍니다.
• compareTo() 메소드의 로직은 다음과 같습니다.
  1. 먼저, 1차 기준인 x좌표를 비교합니다.
  2. 만약 x좌표가 같다면, 그때 2차 기준인 y좌표를 비교합니다.
  3. x좌표가 다르다면, y좌표는 비교할 필요 없이 x좌표의 비교 결과만 반환합니다.

@Override
public int compareTo(Point other) {
    // 1. x좌표 비교
    if (this.x == other.x) {
        // 2. x좌표가 같으면 y좌표 비교 (오름차순)
        return this.y - other.y;
    } else {
        // x좌표가 다르면 x좌표 비교 (오름차순)
        return this.x - other.x;
    }
}

3️⃣ 알고리즘 설계

1. x, y 좌표를 저장하고, Comparable 인터페이스를 구현한 Point 클래스를 정의합니다.
2. N을 입력받고, N개의 Point 객체를 저장할 배열을 생성합니다.
3. for 반복문으로 N개의 좌표를 입력받아 Point 객체를 생성하고 배열에 저장합니다.
4. Arrays.sort(pointArray);를 호출합니다. Java는 Point 클래스에 정의된 compareTo 메소드를 기준으로 배열을 O(N log N) 시간 복잡도로 정렬해 줍니다.
5. 정렬된 배열을 순회하며 각 Point 객체의 x, y 좌표를 형식에 맞게 출력합니다.

---

✅ Java 코드 예제

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;

// Comparable 인터페이스를 구현한 Point 클래스
class Point implements Comparable<Point> {
    int x;
    int y;

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

    @Override
    public int compareTo(Point other) {
        // x좌표가 같다면 y좌표를 기준으로 오름차순 정렬
        if (this.x == other.x) {
            return this.y - other.y;
        }
        // x좌표가 다르다면 x좌표를 기준으로 오름차순 정렬
        else {
            return this.x - other.x;
        }
    }
}

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

        int N = Integer.parseInt(br.readLine());

        Point[] points = new Point[N];

        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());
            points[i] = new Point(x, y);
        }

        // Arrays.sort()를 호출하면 Point 클래스의 compareTo 메소드를 기준으로 정렬됨
        Arrays.sort(points);

        for (int i = 0; i < N; i++) {
            bw.write(points[i].x + " " + points[i].y + "\n");
        }

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

---

⚠️ 실전 주의사항

항목	설명
시간 복잡도	N이 최대 100,000이므로, O(N²) 정렬(버블, 선택 정렬 등)은 시간 초과가 발생합니다. 반드시 O(N log N)을 보장하는 Arrays.sort()를 사용해야 합니다.
Comparable vs Comparator	Comparable은 클래스 자체에 '기본' 정렬 기준을 내장하는 방식입니다. 만약 다른 기준으로도 정렬해야 한다면, 정렬 기준을 외부에서 주입하는 Comparator를 사용하는 것이 더 유연합니다. (람다식으로 간결하게 표현 가능)
compareTo 반환 값	compareTo는 int 값을 반환합니다. 현재객체 - 비교대상객체의 결과가 음수이면 순서 유지, 양수이면 순서 변경, 0이면 동일한 것으로 간주됩니다. 두 정수의 차(a - b)를 반환하는 것은 오름차순 정렬의 표준적인 구현입니다.
입력 성능	N이 크므로 Scanner보다는 BufferedReader를 사용하는 것이 시간 초과를 피하는 데 안전합니다.

---

📝 마무리 요약

✔️ x좌표, y좌표 등 여러 기준으로 정렬해야 하는 다중 조건 정렬 문제입니다.
✔️ 좌표와 같은 복합 데이터를 다룰 때는 별도의 클래스(객체)를 정의하면 코드가 깔끔하고 관리하기 편합니다.
✔️ Java에서 사용자 정의 객체를 정렬하려면 Comparable 인터페이스를 구현하고, compareTo 메소드에 정렬 기준을 명시해야 합니다.
✔️ compareTo 메소드 안에서 1차 기준(x)을 먼저 비교하고, 그 결과가 같을 경우에만 2차 기준(y)을 비교하는 로직을 구현하는 것이 핵심입니다.