[프로그래머스] 가장 큰 수(java)

코딩테스트 연습 - 가장 큰 수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 가장 큰 수

어떻게 생각하고 문제를 풀었는가?

두 정수를 어느 순서로 이어붙이느냐에 따라 만들 수 있는 수의 크기가 다르다는 것은 문자열 두개를 다른 순서로 이었을 때 첫 문자부터 비교를 시작하여 문자 값이 다른 구간이 존재한다라는 것을 의미합니다.

C언어에서는 compare함수로, java에서는 compareTo함수로 이를 구현하고 있습니다.

문자열 s1과 문자열 s2가 입력되었을 때, s1이 사전적으로 s2보다 뒤에 있다면 음수, 같다면 0, 앞에 있다면 양수를 리턴합니다.

이를 활용하여 정답을 유추해낼 수 있겠다고 생각했습니다.

 

코드

import java.util.Arrays;
class Solution {
    public String solution(int[] numbers) {
        String[] stringfied_nums = new String[numbers.length];
        for(int i=0; i<numbers.length; i++){
            stringfied_nums[i] = Integer.toString(numbers[i]);
        }
        Arrays.sort(stringfied_nums, (s1,s2) -> (s2+s1).compareTo(s1+s2));
        String answer = "";
        if(stringfied_nums[0].equals("0")) return "0";
        for(var number : stringfied_nums){
            answer+=number;
        }
        return answer;
    }
}

Arrays는 java에서 제공하는 클래스 메소드입니다.

배열을 다루기 위해 제공된 메소드들이 Arrays에 있으며 sort함수는 Comparator 인터페이스를 받아 주어진 기준에 따른 정렬을 수행할 수 있습니다.

Comparator 인터페이스는 compare함수를 구현해 사용해야 합니다.

람다식으로 배열상 뒤의 문자열이 배열상 앞의 문자열보다 앞에 있어야 한다면 compareTo가 음수를 리턴하여 교환이 이루어지도록 코드를 작성하였습니다.

0으로 이루어진 배열이 입력되었을 경우 단순히 문자열을 이어붙인다면 결과 문자열을 00과 같이 나타납니다.

이를 해결하기 위해 문자열이 0으로 시작하게될 경우 문자열 "0"을 리턴하도록 예외를 두었습니다.

 

Arrays의 정렬 알고리즘

Arrays를 사용하지 않고 직접 삽입 정렬을 사용해 정렬을 시도해보았으나 실행 시간 초과되었습니다.

그래서 자바의 Arrays.sort는 어떤 정렬 알고리즘을 사용하는지 궁금해 찾아보기로 하였습니다.

Arrays (Java SE 11 & JDK 11 ) (oracle.com)

Arrays (Java SE 11 & JDK 11 )

Oracle의 문서에는 배열이 primitive 타입인 경우 Dual-Pivot QuickSort, Object 타입인 경우 Tim Sort를 사용한다고 나와있습니다.

Dual-Pivot QuickSort는 InsertionSort와 QuickSort를 결합한 정렬 알고리즘,

Tim Sort는 InsertionSort와 MergeSort를 결합한 정렬 알고리즘입니다.

 

Dual-Pivot QuickSort는 QuickSort의 성능을 향상시키기 위해 중간 값 분할, 일정 크기보다 작은 파티션에 대해 InsertionSort를 수행하는 정렬 알고리즘입니다.

 

Tim Sort는 MergeSort에 사용되는 추가 메모리 공간, 공간을 위해 소요되는 시간을 더 효율적으로 해결한 정렬 알고리즘입니다.

병합 과정에서 병합을 수행할 필요가 없는 구간을 이분 탐색으로 미리 계산함으로서 시간적 비용을 효율적으로 처리합니다.

Tim Sort에 대한 자세한 설명은 다음 페이지에서 확인해보시면 좋을 것 같습니다.

 

Tim sort에 대해 알아보자 (naver.com)