섹션6. Sort - 7. 좌표 정렬

📌 문제 설명

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

정렬 기준은 다음과 같습니다:

• x값을 기준으로 정렬
• 만약 x값이 같다면 y값 기준으로 정렬

---

📝 입력 & 출력

입력

• 첫 번째 줄에 좌표의 개수 N (3 <= N <= 100,000)
• 이후 N줄에 걸쳐 각각의 x, y 좌표값이 주어짐 (x, y는 양의 정수)

출력

• 정렬된 좌표를 한 줄에 하나씩 출력 (x y)

---

🔹 예제 입력 & 출력

예제 입력 1

5
2 7
1 3
1 2
2 5
3 6

 

예제 출력 1

1 2
1 3
2 5
2 7
3 6

---

💡 해결 방법

• 좌표를 저장할 클래스를 만들고 (Point)
• Comparable 인터페이스를 사용해 정렬 기준을 직접 정의
• Collections.sort()로 정렬

---

💻 코드 구현 (Java)

package partSort;

import java.util.*;

class Point implements Comparable<Point> {
	public int x, y;
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Point o) {
		if (this.x == o.x) return this.y - o.y;
		else return this.x - o.x;
	}
}

public class Problem7 {
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Point> arr = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			int x = kb.nextInt();
			int y = kb.nextInt();
			arr.add(new Point(x, y));
		}
		Collections.sort(arr);
		for (Point o : arr) System.out.println(o.x + " " + o.y);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ Point 클래스 정의 및 정렬 기준 설정

class Point implements Comparable<Point> {
	public int x, y;
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Point o) {
		if (this.x == o.x) return this.y - o.y;
		else return this.x - o.x;
	}
}

• • Comparable을 구현해 정렬 기준을 지정
  • x 기준 정렬, 같으면 y 기준

2️⃣ 좌표 입력 및 정렬

ArrayList<Point> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
	int x = kb.nextInt();
	int y = kb.nextInt();
	arr.add(new Point(x, y));
}
Collections.sort(arr);

• 좌표를 Point 객체로 받아 리스트에 저장 후 정렬

---

⏳ 시간 복잡도 분석

• Collections.sort()는 내부적으로 MergeSort → O(N log N)
• 입력 및 출력: O(N)
• 전체 시간 복잡도: O(N log N)

---

🧩 추가 정리 – Point 클래스와 Comparable 인터페이스 정리

📌 정렬 기준 만들기 – Comparable 인터페이스란?

객체 리스트를 정렬하려면 정렬 기준이 필요합니다. 이때 사용하는 것이 Comparable<T> 인터페이스입니다.

class Point implements Comparable<Point> {
	public int x, y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
    
    @Override
    public int compareTo(Point o) {
        if (this.x == o.x) return this.y - o.y;
        else return this.x - o.x;
    }
}

• Comparable<Point>를 구현하면 두 객체의 크기 비교 규칙을 정의할 수 있습니다.
• 이후 Collections.sort()로 정렬 가능

---

📌 compareTo() 메서드란?

@Override
public int compareTo(Point o) {
	if (this.x == o.x) return this.y - o.y;
	else return this.x - o.x;
}

• this는 현재 객체, o는 비교 대상 객체입니다.

📌 반환값 의미

리턴 값의미

음수	this가 o보다 앞에 위치
0	순서 동일
양수	this가 o보다 뒤에 위치

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런