설명
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
소스 코드 1
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
//좌표 정렬
public class Main {
public static int[][] solution(int N, int[][] arr) {
int[][] tmp = new int[1][2];
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N - 1 - i; j++) {
if (arr[j][0] > arr[j + 1][0]) {
tmp[0][0] = arr[j + 1][0];
tmp[0][1] = arr[j + 1][1];
arr[j + 1][0] = arr[j][0];
arr[j + 1][1] = arr[j][1];
arr[j][0] = tmp[0][0];
arr[j][1] = tmp[0][1];
} else if ((arr[j][0] == arr[j + 1][0]) && (arr[j][1] > arr[j + 1][1])) {
tmp[0][1] = arr[j + 1][1];
arr[j + 1][1] = arr[j][1];
arr[j][1] = tmp[0][1];
}
}
}
return arr;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int arr[][] = new int[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
int ans[][] = solution(N, arr);
for (int i = 0; i < N; i++) {
System.out.println(ans[i][0]+" "+ans[i][1]);
}
}
}
소스 코드 2 (Comparable)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Point implements Comparable<Point>{
public int x;
public int y;
public 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 Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
ArrayList<Point> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
list.add(new Point(x, y));
}
Collections.sort(list);
for (Point val : list) {
System.out.println(val.x + " " + val.y);
}
}
}
Comparble, Comparator 차이점
- Comparable : 클래스 자체에서 객체의 자연스러운 순서를 정의할 때 사용되고, `compareTo` 메서드를 오버라이드 한다.
- Comparator : 외부에서 다양한 기준으로 객체를 비교하기 위해 사용되며 `compare` 메서드를 오버라이드 한다.
Comparable 인터페이스
- `compareTo` 메서드 하나만 가지고 있다.
- `compareTo` 메서드는 현재 객체(this)와 인자로 들어온 책체를 비교한다.
- 양수 반환 : 현재 객체가 비교 대상보다 뒤에 위치해야 한다.
- 0 반환 : 두 객체의 순서를 유지한다.
- 음수 반환 : 현재 객체가 비교 대상보다 앞에 위치해야 한다.
- `Collections.sort()`를 이용하여 `compareTo()`의 반환값을 통해 객체들의 순서를 조정한다.
Comparator 인터페이스
- `compare` 메서드를 가지고 있다.
- 클래스에 Comparable을 구현하지 않고 메서드를 만들어서 Comparator를 상속 받고 자기가 원하는 기준을 세워 비교식을 만들 수 있다.
- 아래와 같이 사용할 수 있다.
List<Person> people = new ArrayList<>();
people.add(new Person("Jun",20));
people.add(new Person("Bae",23));
Comparator<Person> nameComparator = new Comparator<>(){
@Override
public int compare(Person p1, Person p2){
return p1.name.compareTo(p2.name);
}
};
Collections.sort(people,nameComparator);