문제 번호 1181번 : 단어 정렬 - JAVA [자바]

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

1181번: 단어 정렬

문제 설명

 

문자열을 받아 해당 문자열을 기준으로 정렬하는 문제입니다.

단, 같은 문자열의 길이는 문자열의 순서로 출력해야 하고

같은 문자열은 제거해야 합니다.

 

문제 풀이

 

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

해당 문제는 숫자가 아닙니다. 숫자가 아닌 문제를 해결할 때는 Arrays.sort의 Comparator을 재정의해 사용하면 문자 정렬을 효율적으로 사용할 수 있습니다.

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

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

        int n = sc.nextInt();

        String[] array = new String[n];
        
        //버퍼 제거
        sc.nextLine();
        
        //문자열 입력
        for(int i=0; i<n; i++){
            array[i] = sc.nextLine();
        }
        
        
        //문자열 정렬
        Arrays.sort(array, (s1, s2) ->{
            //문자열을 같을 시 comparato로 정렬
            if(s1.length() == s2.length()){
                //문자열의 comparaTo는 문자열 순서로 정렬되도록 내장되어 있음
                return s1.compareTo(s2);
            }
            else{
                //문자열 길이로 정렬함
                return s1.length() - s2.length();
            }
        });
        
        //for문에서 0부터 출력하면 i-1를 비교할 수 없음으로 0을 미리 출력
        System.out.println(array[0]);
        
        //정렬된 문자열 출력
        for(int i=1; i<array.length; i++){
            //같은 문자열 제거
            if(!array[i].equals(array[i-1]))
            System.out.println(array[i]);
        }
    }
}

comparator을 재정의 한 곳 sort의 두 번째 인자가 있는 곳이 람다식으로 comparator의 compara을 ovrriding 한 것입니다.

길이 같으면 s1.compareTo(s2)를 반환하게 되어 있는데 해당 s1과 s2를 사전 순으로 정렬되어 있으면 양수를 아니면 음수를 출력하도록 만들어져 있습니다. 그것을 사용해 sort에서 정렬할 수 있게 됩니다.

 

사실문제를 해결하기 위해서는 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;
        }
    }