[Java] 백준(실버-5) 11650번 - 좌표 정렬하기
문제 풀이
문제를 보고 먼저 2차원 배열을 이용할 수 있다고 느꼈다.
그런데 2차원 배열을 정렬할 때 Arrays.sort() 로는 정렬할 수 없기에 다른 방법을 찾아야 했다.
2차원 배열을 정렬하는 방법을 찾아보니, Arrays.sort() 메서드를 확장하여 람다식을 이용해야 함을 알게되었다.
람다식이란?
람다 함수라고도 불리는 람다식은 프로그래밍 언어에서 사용되는 개념으로 익명 함수(Anonymous functions)를 지칭하는 용어이다.
함수를 하나의 식으로 표현한 것이며, 메소드의 이름이 필요없기 때문에 익명함수의 한 종류라고 볼 수 있다.
람다식의 자세한 내용은 람다식 링크에서 확인하자.
이론으로는 이해가 여려우니 람다식을 활용한 예제를 살펴보자.
1
2
3
public int sum(int a, int b) {
return a + b;
}
sum이라는 메서드를 람다식으로 표현하면 다음과 같다.
1
(int a, int b) -> (return a + b);
이와 같이 람다식을 이용하면 코드를 훨씬 간결하게 고칠 수 있다.
Arrays.sort() 확장
그렇다면 Arrays.sort() 메서드에서 람다식을 어떻게 사용해야 하는지가 궁금했다.
공식문서에서 sort() 메서드를 살펴보았다.
sort() 메서드는 두 가지 인자를 받음을 알 수 있었다. 첫번째 인자로는 제네릭 타입의 배열을 받고 두번째 인자로는 Comparator를 받는다.
첫번째 인자로 받는 제네릭타입의 배열은 무슨 뜻인가 싶었는데, 객체나 클래스, 자료형 모두 타입에 상관없이 배열의 형태로 받을 수 있다고 한다. 2차원 배열을 받아 정렬해야 하니 첫번째 인자로 2차원 배열을 사용하면 된다.
그리고 두번째 인자로 받을 Comparator가 무엇인지 알아보자.
Comparator란?
Comparator는 객체를 비교할 때 사용되는 인터페이스이며, 자기자신과 매개변수로 받은 데이터를 비교하는 Comparable과 다르게 두 매개변수를 비교한다.
여기서 중요한 것은 Comparator는 람다식으로 표현할 수 있다는 것이다.
아이디어 도출
Arrays.sort() 메서드를 확장하여 2차원 배열과 Comparator를 매개변수로 하여 정렬할 수 있음을 알았으니 어떻게 코드를 작성할지 생각해보자.
- (x,y) 좌표를 N개 담을 2차원 배열 arr이 있다면 arr[0][0]부터 arr[N][0]까지 순회하며 x좌표, 즉 첫번째 원소를 오름차순으로 정렬해야 한다.
- x좌표를 기준으로 오름차순으로 정렬하면서 연속된 x좌표가 같다면, 즉 arr[i][0]과 arr[i+1][0]을 비교하며 두 값이 같다면 y좌표인 arr[i][1]과 arr[i+1][1]를 비교하면 된다.
그러면 Arrays.sort() 메서드를 확장해서 2차원 배열과 Comparator를 인자로 주는 코드를 작성해보자.
1
2
3
4
5
6
7
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]) return o1[1] - o2[1];
else return o1[0]-o2[0];
}
});
위와 같이 Comparator를 사용할 수 있지만, 위에서 언급했듯이 Comparator는 람다식으로 표현할 수 있다.
1
2
3
4
Arrays.sort(arr, (o1, o2) -> {
if(o1[0] == o2[0]) return o1[1] - o2[1];
else return o1[0] - o2[0];
});
람다식은 별도로 메서드를 구현하지 않고 함수로 간편하게 작성할 수 있다.
2차원 배열을 정렬하는 방법에 대해서 배웠으니 문제의 솔루션 코드를 작성해보자.
1
2
3
4
5
6
7
8
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][2];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
먼저 N을 입력받고, x,y좌표를 N개씩 담을 arr 2차원배열을 선언하자.
그리고 N만큼 반복하며 N개의 x,y좌표를 입력받아 arr 배열에 저장한다.
1
2
3
4
5
6
7
8
Arrays.sort(arr, (o1, o2) -> {
if(o1[0] == o2[0]) return o1[1] - o2[1];
else return o1[0] - o2[0];
});
for(int i=0; i<arr.length; i++) {
bw.write(arr[i][0] + " " + arr[i][1] + "\n");
}
2차원 배열 arr를 x좌표 기준으로 오름차순으로 정렬하다가 연속으로 같은 값을 가지는 x좌표가 있다면 y좌표를 기준으로 오름차순으로 정렬하도록 작성한다.
마지막으로 정렬된 2차원 배열의 x,y 좌표를 공백과 함께 출력하면 된다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][2];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, (o1, o2) -> {
if(o1[0] == o2[0]) return o1[1] - o2[1];
else return o1[0] - o2[0];
});
for(int i=0; i<arr.length; i++) {
bw.write(arr[i][0] + " " + arr[i][1] + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
회고
- 2차원 배열을 정렬하는 방식 중에서 람다식과 Comparator에 대해서 공부할 수 있었다.
- Comparator와 Comparable의 차이점을 명확하게 알고 사용해야겠다.