문제 번호 11650번 : 좌표 정렬하기 - JAVA [자바]

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

 

문제 설명

 

좌표를 x축을 기준으로 x축이 같으면 y축으로 비교하여 정렬하는 문제입니다.

 

보고 오기를 추천하는 게시물

 

https://kkungchan.tistory.com/300

Java - comparable과 comparator에 대해

 

문제 풀이

 

해당 문제는 이중 배열과 Arrays.sort을 사용해서 풀도록 하겠습니다.

정렬 알고리즘을 사용해 풀어도 괜찮지만 arrays.sort을 사용하면 tim sort와 LegacyMergeSort 정렬 방식으로 사용해 효율이 매우 좋습니다.

comparator도 알아볼 겸 sort를 사용해 문제를 해결해 보겠습니다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[][] array = new int[n][2];

        for(int i=0; i<n; i++){
           array[i][0] = sc.nextInt();
           array[i][1] = sc.nextInt();
        }


        /*
        Arrays.sort는 LegacyMergeSort 혹은 Tim sort 알고리즘을 사용한다.
        Comparator이 존재할 경우 Tim sort를 사용해 정렬한다.
        compare을 재정의해 y값을 비교 할 수 있도록 한다.
        int[]가 인자가 되고 e1의 [0]은 x값 e1[1]은 y값이 될 것이다.
        e2도 마찬가지 이고 Tim sort로 해당 값을 비교해 정렬할 것이다.
         */

        /*
        Arrays.sort(array, new Comparator<int[]>() {
            @Override
            public int compare(int[] e1, int[] e2) {
                if(e1[0] == e2[0]) {
                    return e1[1] - e2[1];
                }
                else {
                    return e1[0] - e2[0];
                }
            }
        });
        */
        //compare을 함수를 람다식으로 구현에 Comparator 인자를 넘겨주는 형식으로 좀 더 간단하도록 구현했다.
        Arrays.sort(array,(e1, e2) -> {
            if (e1[0] == e2[0]) {
                return e1[1] - e2[1];
            }else {
                return  e1[0] - e2[0];
            }
        });

        for(int i=0; i<n; i++){
            System.out.println(array[i][0]+ " " + array[i][1]);
        }

    }
}

 

사실문제를 해결하기 위해서는 Tim sort, 람다식, Comparable과 Comparator에 대해 기본적인 지식이 있어야 합니다. 게시물로 모두 정리해 놓고 싶지만 정렬에 너무 많은 시간을 쓰는 거 같아서.. 다음에 꼭 기회가 되면 게시하도록 하겠습니다. 물론 overriding에 대한 개념도 가지고 있어야 합니다. 혹시나 overriding이 궁금하신 분들은 아래 게시물을 참고해 주세요.

https://kkungchan.tistory.com/176

Java 기초 상속(6) - overriding

 

 

해당 코드는 comparator을 인자로 전달해 줌으로 Tim sort을 사용해 정렬이 됩니다. Tim sort는 이진삽입 정렬과 합병 정렬을 조합한 매우 효율이 좋은 정렬 방식입니다.

sort에 있는 comparator를 overriding 해주는데 이유는 sort의 comparator은 x축이 같은 때 y축으로  비교하는 비교 기준을 모르기 때문에 그것을 알려주는 과정입니다. 

아래 코드는 java.util 라이브러리 안에 제공해 주는 sort함수표입니다. 코드에서 sort를 사용한다는 것은 아래 함수를 사용한다는 의미입니다. 해당 함수를 보면 comparator의 여부로 sort의 여부를 다르게 결정한 다는 것을 알 수 있습니다. 저희가 궁금한 건 c를 어떻게 사용하는지입니다. 그럼 c를 찾아보겠습니다.

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

 Tim sort을 타고 들어가다 보면 binarySort를 발견할 수 있습니다. 이유는 Tim sort가 이진 삽입 정렬과 합병 정렬을 합친 것이기 때문입니다. 찾아보면 병합 정렬도 찾아볼 수 있습니다. 중요한 건 c를 비교하는 데 사용한다는 것입니다. c.compara에 인자 두 개를 넣은 다음에 그것이 0보다 작으면 두 원소의 위치를 변경하고 0보다 크면 변경하지 않습니다. 그렇다면 compara을 우리의 입맛에 맞게 고치면 해당 비교를 어떤 기준으로 해야 할지 알려줄 수 있을 것입니다.

자바의 대부분 정렬은 compara을 재정의 하는 방식으로 이루어집니다. 게시물을 게시하지 않아 단순하게 설명하지만 시간이 되면 꼭 게시하도록 하겠습니다.

    private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                       Comparator<? super T> c) {
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        for ( ; start < hi; start++) {
            T pivot = a[start];

            // Set left (and right) to the index where a[start] (pivot) belongs
            int left = lo;
            int right = start;
            assert left <= right;
            /*
             * Invariants:
             *   pivot >= all in [lo, left).
             *   pivot <  all in [right, start).
             */
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (c.compare(pivot, a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /*
             * The invariants still hold: pivot >= all in [lo, left) and
             * pivot < all in [left, start), so pivot belongs at left.  Note
             * that if there are elements equal to pivot, left points to the
             * first slot after them -- that's why this sort is stable.
             * Slide elements over to make room for pivot.
             */
            int n = start - left;  // The number of elements to move
            // Switch is just an optimization for arraycopy in default case
            switch (n) {
                case 2:  a[left + 2] = a[left + 1];
                case 1:  a[left + 1] = a[left];
                         break;
                default: System.arraycopy(a, left, a, left + 1, n);
            }
            a[left] = pivot;
        }
    }

 

 

compara을 x축이 같으면 y을 비교한는 식으로, y축의 뺌으로 함수를 반환해주고 x축이 다르면 x축의 뺌으로 반환해줍니다. 이유는 compare의 비교 방식은 양수면 비교한 값이 정렬이 된 것이고 음수면 위치를 변경하는 식으로 되어 있기 때문입니다.(의례적으로 그렇습니다. 개발자가 물론 임의로 변경할 수 있습니다.)

람다식은 함수 이름을 지우고 화살표를 사용해 가독성을 높인 것이라 생각하시면 됩니다.