[Algorithm] 좌표정렬 / Comparable<?>, compareTo(Object o)

좌표데이터를 정렬할 때 편리하게 사용되는 클래스 Comparable과 Comparable의 메서드 compareTo가 있다.

먼저 간단한 좌표정렬 문제와 풀이를 확인하자. 

 

 

문제 : 백준 11651

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

예제 입력

5
0 4
1 2
1 -1
2 2
3 3

 

예제출력

1 -1
1 2
2 2
3 3
0 4

 

 

문제는 x, y 데이터가 주어지면

1. 먼저 y값이 증가하는순으로 데이터를 정렬하고

2. y값이 동일한 경우에는 x값이 증가하는 순으로 데이터를정렬

하는 것이다.

 

아래는 Comparable<?> 클래스와 compareTo(Object o)메서드를 사용한 풀이다.

풀이

import java.util.*;

class Compare implements Comparable<Compare>{
	int x,y;
	Compare(int x,int y){ 
		this.x=x; this.y=y;
	}
	public int compareTo(Compare c){
		if(this.y==c.y) return this.x-c.x;
		else return this.y-c.y;
	}
}
class Main{
	public static void main (String args[]){
		Scanner in= new Scanner(System.in);
		int n = in.nextInt();
		ArrayList<Compare> cList=new ArrayList<>();
		for(int i=0;i<n;i++){
			cList.add(new Compare(in.nextInt(), in.nextInt()));
		}
		Collections.sort(cList);
		for(Compare c:cList) System.out.println(c.x+" "+c.y);
	}
}

 

 

 

Collections.sort()

 

먼저 자동정렬기능을 가진 Collections.sort()에 대해 알아보자.

static메서드인 sort()메서드에는 Comparable인터페이스를 구현한 객체가 매개변수로 들어올 수 있다.

sort()메서드는 들어온 데이터를 순서대로 정렬한다. 

이때 !! 순서를 정렬할 때 사용하는 것이 바로 Comparable객체의 compareTo메서드다.

 

그렇다면 사용자가 원하는 순서대로 데이터를 정렬하려면 어떻게해야할까?

compareTo메서드를 overriding 하면된다.

 

풀이코드를 보면, Comparable<T>을 구현한 Compare 클래스가 있고 그 안에 compareTo메서드를 오버라이딩하고 있다.

Comparable 인터페이스의 특징은 '자기자신'과  compareTo메서드의 인자값으로 '들어온 객체'를 비교하여 정렬을 만든다는 것이다. 그렇기에 Comparable<T>의 제너릭 타입을 자기자신으로 준다. 

 

그리고 Overriding된 compareTo메서드에서 원하는 정렬을 만들어줄 식을 세우면 Collections.sort() 를 이용해 정렬을 사용할 수 있다. 

 

참고 : 내림차순 Collections.sort()로 내림차순을 정렬하고싶으면 두번째 인자값에 Comparator.reverseOrder()을 주면된다.

내림차순 - Collections.sort(Comparable<T>구현자, Comparator.reverseOrder());

오름차순 - Collections.sort(Comparable<T>구현자, Comparator.naturalOrder());

 

 

코드해석

 

코드를 보자

x,y 값을 Comparable을 구현하고있는 Compare클래스를 객체생성할 때 인자값으로 보낸다.

그리고 Compare객체를 ArrayList에 담는다.

그 다음, 자동 정렬기능을 가진 Collections.sort()메서드에 매개변수로 Compare객체를 담은 ArrayList를 넣어준다. 

그러면 자동으로 compareTo메서드에 가서 비교하며 정렬하게되는데,

위 코드에는 Compare클래스에서 compareTo메서드가 오버라이딩되어있기 때문에

Compare클래스의 compareTo메서드가 실행된다.

 

compareTo메서드에서는

문제의 요구사항대로 비교하는 y값을 기준으로 순서를 정하되, y값이 동일하면 x값을 비교하여 정렬한다.

 

 

 

그외

 

Comparable 인터페이스를 사용하지 않더라도 Comparator를 사용하여 정렬할 수도 있다. 아래 두 블로그를 참조하자!

Comparable 과 Comparator의 차이

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

자바 [JAVA] - Comparable 과 Comparator의 이해

 

 

Collections.sort()의 구동방법

https://wjheo.tistory.com/entry/Java-%EC%A0%95%EB%A0%AC%EB%B0%A9%EB%B2%95-Collectionssort

Java 정렬방법 Collections.sort()

 

Java 정렬방법 Collections.sort()