https://www.acmicpc.net/problem/11650
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
접근 방법 / 해결 방법
2차원 배열을 사용한다면 쉽게 해결이 될 것 같았다. int[ 입력값 ]{ { x좌표1 , y좌표1 } , { x좌표2 , y좌표2 } , { x좌표3 , y좌표3 } , { x좌표4 , y좌표4 } ...... } 이렇게 값을 넣고 정렬을 하면 되겠다 싶었다.
코드로 옮겨보자.
.
.
.
int[][] location = new int[N][2];
for(int i = 0; i < location.length; i++)
{
st = new StringTokenizer(bf.readLine() , " ");
for(int j = 0; j < 2; j++)
location[i][j] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < location.length; i++) {
// 유사 버블 정렬
for(int j = 0; j < location.length-1; j++ ) {
if(location[j][0] > location[j+1][0]) {
int tmp = location[j][0];
location[j][0] = location[j+1][0];
location[j+1][0] = tmp;
tmp = location[j][1];
location[j][1] = location[j+1][1];
location[j+1][1] = tmp;
}else if(location[j][0] == location[j+1][0]) {
if(location[j][1] > location[j+1][1]) {
int tmp = location[j][1];
location[j][1] = location[j+1][1];
location[j+1][1] = tmp;
}
}
}
}
.
.
.
버블 정렬과 비슷하다. 문제에서 x좌표가 같다면 y값을 기준으로 정렬하라고 했으니 if(location[j][0] > location[j+1][0]) 조건을 추가해주었다. 자신만만하게 코드를 제출하였으나, 결과는...
입력값은 100,000이고 시간 제한은 1초인데, 시간 복잡도가 O(N²) 알고리즘인 버블 정렬을 사용했으니( 심지어 보통 버블 정렬보다 실행 코드 수가 더 길다. ) 시간 초과가 나는 것이 당연하다.
결국 달리 떠오르는 아이디어도 없었으므로 내장 함수를 사용하기로 결심했다. 그런데 나는 java.util 패키지에 있는 Arrays.sort()를 자주 사용했었는데, 무심코 쓰려다 드는 의문 한가지. Arrays.sort()로 다차원 배열도 정렬이 가능하던가?
그냥 사용하면 불가능하다. java.lang.ClassCastException: I cannot be cast to java.lang.Comparable 오류가 발생한다. 구글링 결과 원인은 비교 기준이 구현되어 있지 않기 때문에 캐스팅에 실패했기 때문이라고 한다.
Arrays.sort()로 정렬하기 위해선 Comparable, Comparator 인터페이스를 구현하여 정렬기준을 추가해 줘야 한다.
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N = Integer.parseInt(bf.readLine());
int[][] dat = new int[N][2];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(bf.readLine() , " ");
dat[i][0] = Integer.parseInt(st.nextToken());
dat[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(dat , new Comparator<int[]>(){
@Override
public int compare(int[] o1 , int[] o2) {
return o1[0] != o2[0] ? o1[0]-o2[0] : o1[1]-o2[1];
}
});
for(int i = 0; i < N; i++) {
bw.write(dat[i][0] + " " + dat[i][1]+"\n");
}
bw.flush();
}
}compare() 메서드를 오버라이드하여 원하는 정렬 기준을 명시해 준다. int[] 타입 변수인 o1[0]과 o2[0]이 같지 않으면 o1과 o2의 x좌표를 비교하고, 같다면 o1과 o2의 y좌표를 비교하여 정렬한다.
배운점
comparetor인터페이스는 처음 접하였는데, sort에서 어떤 역할을 하는지 궁금하여 자세히 알아보았다.
참고 -> https://st-lab.tistory.com/243
객체 간의 비교를 지원해준다는 점에서 무척 유용하다고 느껴졌다.
본 문제를 푼 다른 사람의 코드를 몇 개 보았는데, 똑같이 comparetor 인터페이스를 통해 해결한 코드가 대부분이었다.
많은 사람들이 사용한다는 점에서 comparetor 인터페이스를 더 잘 알고 있어야겠다고 느꼈다.
