Baekjoon 문제 풀기 (11650번 : 좌표 정렬하기) Java
11650번 : 좌표 정렬하기Permalink
1. 문제읽기Permalink
커스텀 정렬 문제
정렬을 내맘대로 기준을 세워서 할 수 있는지 물어보는 문제이다.
2. 제출 코드Permalink
compare 오버라이드하는 것은 다른 문제에서 해봐서 쉬웠는데, 리턴 값의 개념이 정확히 와닿지 않아서 이것 저것 해보다가 성공했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
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());
List<int[]> arr = new ArrayList<>();
// List에 좌표 넣기
while(n --> 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int[] tmp = new int[2];
tmp[0] = Integer.parseInt(st.nextToken());
tmp[1] = Integer.parseInt(st.nextToken());
arr.add(tmp);
}
Collections.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] < o2[0]) {
return o1[0] - o2[0];
} else if(o1[0] == o2[0]) {
return o1[1] - o2[1];
}
return 1;
}
});
StringBuilder sb = new StringBuilder();
for(int[] i : arr) {
sb.append(i[0]).append(" ").append(i[1]).append("\n");
}
System.out.println(sb);
}
}
3. 공부할 것Permalink
위의 제출 코드에서 고치면 좋을 부분이 3군데 정도 있다.
- 오버라이드 대신 람다식 사용하기
Collections.sort대신arr.sort사용하기- 리턴값 보기 좋게 수정하기
리턴 값에 대해서는 따로 조금 더 공부해야했다.
의문이였던 점이 왜 어떤 것이 큰지 정해주지 않아도 리턴값으로 오름차순, 내림차순이 결정되는가? 였다.
대부분의 정렬 알고리즘은 두 요소를 비교하여 두 요소의 위치를 정하는 방법을 사용하는데, 여기서도 똑같이 적용시켜주는 것이다.
{1, 2} 를 예로 들면, 왼쪽에서 오른쪽을 빼면 음수가 나온다. {1, 2} 는 이미 오름차순이므로 위치를 바꿔줄 필요가 없다. 따라서 쉽게 정리하자면 음수일 때는 위치를 바꾸지 않는다.
반대로
{2, 1} 일 때는 왼쪽에서 오른쪽을 빼면 양수가 나온다. 오름차순 {1, 2} 를 만들려면 위치를 바꿔줘야하기 때문에 양수일 때는 위치를 바꿔준다.
따라서 어떤 것이 큰지 if문을 사용하지 않아도 이러한 로직으로 인해 왼쪽 값에서 오른쪽 값을 뺀 리턴값으로 오름차순으로 정렬할 수 있다.
내림차순으로 정렬하고 싶다면 o1 - o2 대신 o2 - o1을 리턴해주면 된다.
1, 2, 3번을 적용하여 코드를 수정해주면 아래와 같이 간단하게 수정할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ11650 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<int[]> arr = new ArrayList<>();
// List에 좌표 넣기
while(n --> 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int[] tmp = new int[2];
tmp[0] = Integer.parseInt(st.nextToken());
tmp[1] = Integer.parseInt(st.nextToken());
arr.add(tmp);
}
arr.sort((o1, o2) -> {
if(o1[0] == o2[0]) {
return o1[1] - o2[1];
} else {
return o1[0] - o2[0];
}
});
StringBuilder sb = new StringBuilder();
for(int[] i : arr) {
sb.append(i[0]).append(" ").append(i[1]).append("\n");
}
System.out.println(sb);
}
}
댓글남기기