[sort] 좌표 정렬

좌표 정렬 문제를 풀며 구글링을 하다가 좋은 개념들을 배워서 꼭 기록해야겠다고 생각했다.

---

문제)

 

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

11650번: 좌표 정렬하기

---

해결방법은 두가지가 있는 것 같다.

1. Comparable 인터페이스의 구현클래스(Point)를 작성하고, compareTo 함수를 오버라이딩해 좌표정렬

2. Arrays.sort()의 Comparator를 작성해 좌표정렬

          - 람다식 작성법 

---

1-1) Comparable 인터페이스의 구현클래스(Point 클래스)를 작성

class Point implements Comparable<Point>{
	public int x, y;
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

x좌표와 y좌표를 가진 Point클래스와 생성자를 간단히 만들어주었다.

 

 

1-2) 이때, Comparable에서 정렬할 때 사용하는 compareTo함수를 오버라이딩해줌으로써 우리가 원하는대로 정렬이 가능하다.

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

x좌표를 기준으로 정렬하되, x좌표가 같다면 y좌표로 넘어가 y좌표끼리 정렬을 시키는 코드이다.

여기서 compareTo함수의 리턴값이 음수라면 오름차순 / 양수라면 내림차순을 뜻하기 때문에,

x좌표끼리, y좌표끼리 뺄셈을 해줌으로써 리턴해준다.

 

 

1-3) 입력받을 때에는 ArrayList<Point>로 받아주고, Point 객체를 ArrayList에 추가해준다.

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)를 해주면, Comparable의 오버라이딩된 함수 compareTo가 실행되며 좌표들이 정렬된다.

Collections.sort(arr);

 

 

[전체 코드]

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;
	}
}

class Main {	
	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);
	}
}

---

2. Arrays.sort()의 Comparator를 작성

이 방법 또한 compare함수를 자신만의 방법으로 오버라이딩하는 것은 매한가지이다.

 

2-1) 우선 입력받을 때에 int[][2]의 크기를 가진 정수형 2차원 배열으로 입력받는다.

Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int[][] arr = new int[n][2];
for(int i=0; i<n; i++) {
	arr[i][0] = kb.nextInt();
	arr[i][1] = kb.nextInt();
}

arr[i][0] 에는 x좌표, arr[i][1] 에는 y좌표들이 들어가게 되는 형태이다.

 

2-2) 오버라이딩한다.

그 전에 sort함수의 기본형부터 찾아보면 이러하다.

public static <T> void sort(T[] a, Comparator<? super T> c)

T[] 에는 어떠한 객체배열이든 들어갈 수 있다. (자료형, 오브젝트, 클래스 등등)

우리는 2차원 배열 int[][]를 쓸 것이기 때문에 T = int[] 가 된다.

때문에 다음과 같이 compare함수를 오버라이딩할 수 있다.

Arrays.sort(arr, new Comparator<int[]>() {		
	@Override
	public int compare(int[] e1, int[] e2) {
		if(e1[0] == e2[0]) {		// 첫번째 원소가 같다면 두 번째 원소끼리 비교
			return e1[1] - e2[1];
		}
		else {
			return e1[0] - e2[0];
		}
	}
});

 

2-3) 그러나, 람다식을 활용하면 훨씬 간단해진다.

앞서 람다식에 대해 알아보자. 기본형은 다음과 같다.

(매개변수1, 매개변수2, ...) -> {함수;}

 

쉬운 이해를 위해 몇가지 예를 살펴보자.

// 람다식 X
public int sum(int a, int b) {
	return a + b;
}
 
// 람다식 O
(int a, int b) -> {return a + b;}

 

 

위에서 작성했던 Arrays.sort를 람다식으로 표현하면 다음과 같다.

Arrays.sort(arr, (e1, e2) -> {
	if(e1[0] == e2[0]) {
		return e1[1] - e2[1];
	}
	else {
		return e1[0] - e2[0];
	}
});

이렇게 arr배열의 좌표정렬이 가능하다.

 

 

2-4) 출력 - arr[i][0] 과 arr[i][1] 를 출력하면 차례대로 x좌표와 y좌표가 출력된다.

for(int i=0; i<n; i++) 	
	System.out.println(answer[i][0] + " " + answer[i][1]);

 

 

[전체 코드]

import java.util.*;

public class Main {
	public int[][] solution(int n, int[][] arr){
		Arrays.sort(arr, (e1, e2) -> {
			if(e1[0] == e2[0])
				return e1[1] - e2[1];
			else
				return e1[0] - e2[0];
		});
		
		return arr;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[][] arr = new int[n][2];
		for(int i=0; i<n; i++) {
			arr[i][0] = kb.nextInt();
			arr[i][1] = kb.nextInt();
		}
		int[][] answer = T.solution(n, arr);
		for(int i=0; i<n; i++) 	System.out.println(answer[i][0] + " " + answer[i][1]);
	}
}

---

람다식, Comparator, Comparable 등등 유용한 개념을 알아가는 기회가 되어 좋았다.

아래의 포스팅이 정말 많은 도움이 되어 참고하였다.

https://st-lab.tistory.com/110

[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]