문제 url:
좌표 정렬하기
문제:
🤔 문제 알아보기
이번 문제는 2차원 배열을 이용한 정렬 방법이다. 2차원 배열에 입력값을 넣은 다음, x좌표의 인덱스 값을 활용하여 비교한 후, 정렬하되 만약 x좌표가 같은 값이면 y좌표를 기준으로 오름차순 정렬한다.
사실 필자는 2차원 배열을 활용하면 시간 복잡도에 문제가 발생할 것이다.
라고 판단하여 다르게 풀었다가 출력을 못해 풀지 못했다.해당 문제를 풀지 못해 타 블로그를 참조를 거의 했는데, 이번 문제는 Arrays.sort()에 존재하는 Comparactor 인터페이스를 활용한 문제라고 한다.
아래의 코드가 우리가 사용할 메서드이다.
해당 문제를 풀기 위해 Comparactor와 Comparable에 대한 내용을 선수로 알아놓으면 좋다. 또한 이번 문제는 람다식(익명 함수)를 이용해 문제를 풀고자 한다.
Comparactor와 Comparable에 관한 내용, 람다식(익명 함수)에 대한 내용을 정리하고자 하는데, 머리도 나쁘고 내용 자체도 많아 시간이 걸릴 듯 하다.
이번에는 코드 리뷰로만 진행하되 꼭 해당 부분을 정리하도록 하겠다!
🐱👤 실제 코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// x y 좌표가 N개만큼 있을것이며,
// 뒤의 2는 X, Y좌표 총 두 개를 받으니 2가 된다.
int[][] arr = new int[N][2];
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
//arr[i][0] : i번째의 x 좌표를 의미
arr[i][0] = Integer.parseInt(st.nextToken());
//arr[i][1] : i번째의 y 좌표를 의미
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, (e1, e2) -> {
if(e1[0] == e2[0]) {
return e1[1] - e2[1];
} else {
return e1[0] - e2[0];
}
});
StringBuilder sbd = new StringBuilder();
for(int i = 0; i < N; i++) {
sbd.append(arr[i][0] + " ").append(arr[i][1]).append("\n");
}
System.out.println(sbd);
}
}
Arrays.sort()메서드 위의 내용은 주석에 대부분 정리를 하여 크게 어렵지 않을 것이다.
그렇다면 이제 Arrays.sort()메서드 로직을 꼼꼼하게 살펴보도록 하자
Arrays.sort()를 나름 정리를 했다고 했는데... 역시 아이언이 승급해봐야 브론즈이다.
위에서도 설명했지만, 우리는 오버로딩된 sort중 해당 메서드를 사용하고자 한다.
빠진 내용이 있어 첨언하자면 해당 sort()메서드는 배열 a를
Comparactor c의 규칙으로 정렬을 하겠다는 의미이다.그럼 이해를 위해 간략하게 Comparactor에 대해서 설명을 해보도록 하겠다.
Comparactor 인터페이스는 객체를 비교하기 위해 사용하는 데, 그렇다면 왜 객체를 비교하는 것인가?
보통 primitive type(원시 타입)은 자바에서 비교 연산자를 제공하기 때문에
(>=, ==, <=) 등쉽게 비교할 수 있지만, 객체는 무엇을 비교해야 할 지 모른다.만약, Point라는 클래스가 있다고 가정하자,
class Point() { String name; int point; Point(String name, int point) { this.name = name; this.point = point; } } Point p1 = new Point("A" , 100); Point p2 = new Point("B" , 80);사람은 바로바로 point를 보고 이걸로 비교할 수 있다는 것을 알아차리지만,
우리의 친구는 그렇지 않다. 객체안에 있는 point 필드를 이용해 비교를 해줘야만 비교를 할 수 있는 것이다.이렇듯, 객체를 가지고 비교를 하고자 할 때 Comparactor 인터페이스를 사용할 수 있는 것이다.
이해한 바를 짧게 녹이려고 하니 이해가 어려울 수도 있고, 잘못된 내용이 포함될 수 있다. 중요한 건 객체를 비교하기 위해 사용한다는 것만 일단 이해하고 있으면 될 것 같다.
그럼 이제 다시 본론으로 넘어와서
Arrays.sort(arr , <해당 부분>...) 이 해당 부분에 속한 것이 Comparactor로 받겠다는 것인데, 왜 뜬금 없이 e1, e2를 받는 것인가?
Arrays.sort(arr, (e1, e2) -> {
if(e1[0] == e2[0]) {
return e1[1] - e2[1];
} else {
return e1[0] - e2[0];
}
});이는 람다식으로 표현하여 객체를 파라미터로 보낸 것인데,
여기서 람다식이란??
람다식은 쉽게 말해 메서드를 하나의 식으로 표현한 것을 말하는데class int sum(int a, int b) { return a + b; } int c = sum(a , b);우리가 흔히 함수를 만들고 활용할 때 위와 같이 사용한다. 하지만 람다식을 이용하게 되면 이러한 과정이 필요 없다.
(int a, int b) -> {return a + b}이런 식으로 나타내면 간단히 sum 함수와 동일한 결과를 가져올 수 있다.
그래서 람다식으로 표현하면 가독성이 좋아지고 메서드의 이름(ex. sum)과 return 타입(ex. int)을 지정해줄 필요 없어 일회성 함수(한번 쓰고 마는)를 사용할 때 자주 쓰인다고 한다.그래서 메서드 이름이 없다고 해서, 익명함수라고도 한다.
지금까지 람다식을 활용한 Arrays.sort()방식을 살펴보았고, 람다가 아닌 직접 익명함수로 Comparactor 객체를 생성하여 주입하는 방법도 살펴 보겠다.
🐱👤 실제 코드 Comparactor 객체 생성
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// x y 좌표가 N개만큼 있을것이며,
// 뒤의 2는 X, Y좌표 총 두 개를 받으니 2가 된다.
int[][] arr = new int[N][2];
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
//arr[i][0] : i번째의 x 좌표를 의미
arr[i][0] = Integer.parseInt(st.nextToken());
//arr[i][1] : i번째의 y 좌표를 의미
arr[i][1] = Integer.parseInt(st.nextToken());
}
// Comparactor 객체를 익명함수로 생성
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]) { // i 번째 x값과 i+1번 째 x값이 같다면
return o1[1] - o2[1]; // y좌표의 오름차순으로 나타냄
} else {
return o1[0] - o2[0];
}
}
});
StringBuilder sbd = new StringBuilder();
for(int i = 0; i < N; i++) {
sbd.append(arr[i][0] + " ").append(arr[i][1]).append("\n");
}
System.out.println(sbd);
}
}
Comparactor 인터페이스 객체를 생성하면, 반드시 compare()메서드를 오버라이딩 하도록 되어 있다.
🤢 회고
2차원 배열을 사용하는 것은 생각했지만, 이러한 접근 방식은 처음이라 빠르게 답지?를 보기 잘한 것 같다. 해당 문제를 풀면서 Arrays.sort()메서드에 대해서 조금 더 자세히 정리하면 좋을 것 같고, 또 람다식, Comparable, Comparactor에 대해서 확인하는 시간을 가질 수 있었다.
이후로는 람다식과 Comparable, Comparactor에 대해서 살펴보고자 한다.
💜 참고자료
[백준] 11650번 : 좌표 정렬하기 - JAVA [자바] Stranger's LAB
