Baekjoon 문제 풀기 (11650번 : 좌표 정렬하기) Java

11650번 : 좌표 정렬하기

1. 문제읽기

---

커스텀 정렬 문제

정렬을 내맘대로 기준을 세워서 할 수 있는지 물어보는 문제이다.

2. 제출 코드

---

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. 공부할 것

---

위의 제출 코드에서 고치면 좋을 부분이 3군데 정도 있다.

1. 오버라이드 대신 람다식 사용하기
2. Collections.sort 대신 arr.sort 사용하기
3. 리턴값 보기 좋게 수정하기

리턴 값에 대해서는 따로 조금 더 공부해야했다.
의문이였던 점이 왜 어떤 것이 큰지 정해주지 않아도 리턴값으로 오름차순, 내림차순이 결정되는가? 였다.
대부분의 정렬 알고리즘은 두 요소를 비교하여 두 요소의 위치를 정하는 방법을 사용하는데, 여기서도 똑같이 적용시켜주는 것이다.

{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);
    }
}