1. 문제 설명 📌

배열을 정렬해서, 인접한 두 값의 차의 최대값을 반환해라

2. 접근 방식 🗃️

KEY WORD: RADIX SORT

해당 문제는 java의 native 정렬 알고리즘을 활용해도 되지만, 기수 정렬(Radix-sort)를 활용해보고 싶어서, 해당 알고리즘을 활용해서 문제를 풀어보았다.

그저 정의 그대로 구현한 것 뿐이라, 따로 접근 방식을 설명할 것이 없다. Radix-sort에 대해 모르시는 분들은 다음 링크에 내용이 적혀 있으니 한번 보고 오는 것을 추천 드린다.

https://dalcheonroadhead.tistory.com/558

3. 코드 소개 🔎

import java.util.*;

class Solution {
    public int maximumGap(int[] nums) {

        if(nums.length < 2) return 0;
        int [] arr = new int [nums.length + 1];
        for(int i = 0; i < nums.length; i++){
            arr[i+1] = nums[i];
        }
        radix_sort(arr, 0);
        int max_GAP = 0;
        for(int i = 2; i < arr.length; i++){
            max_GAP = Math.max(max_GAP, arr[i]-arr[i-1]);
        }

        return max_GAP;
    }

    private void radix_sort (int [] arr, int digit) {
        int [] nums = new int [10];
        int [] result = new int [arr.length];
        // 1. 현 자릿수를 통해 자릿수 배열 만들기
        for (int i = 1; i < arr.length; i++){
            nums[(int) (arr[i] / (Math.pow(10, digit))) % 10]++;
        }
        // 0. 기저 조건
        if(digit == 9) return;

        // 2. 누적합 만들기
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i-1];
        }
        // 3. 자릿수 배열을 활용해 값 정렬
        for (int i = arr.length-1; i >= 0; i--) {
            int now_digit = (int)(arr[i]/Math.pow(10,digit))%10;
            result[nums[now_digit]] = arr[i];
            nums[now_digit]--;
        }

        for (int i = 1; i < result.length; i++) {
            arr[i] = result[i];
        }
        radix_sort(arr, digit+1);
    }

}

4. 배운 것들 🎯

(1) 착각하고 있던 기저 조건

처음엔 기저 조건을

if(nums[0] == arr.length -1) return;

으로 만들었다. 즉 '모든 수가 현재 자릿수를 체크했을 때, 값이 0이면 종료한다.' 의 뜻이다. 언뜻 보면 맞는 것 같다. 예를 들어 [1,2,3,4,5,6]이 있다고 치면 10의 자릿수를 확인할 때부터 모든 수의 자릿수가 0이 되므로 더 이상 계산할 필요가 없다는 것을 보여주기 때문이다. 하지만 리트 코드를 통해 다음 반례를 찾을 수 있었다.

[1, 10000000]
해당 입력값은, 10의 자리에서 모든 원소의 자릿수가 0이 된다. 1의 자리에서 정렬 했을 시 [10000000, 1]이 되어버림으로, 정렬을 10의 자리에서 멈추면 오답이 되어버린다!

다시 생각해보니 기저 조건에 골머리를 쌀 필요가 없었다. 기수 정렬의 장점은 최대 자릿수 만큼 반복하면 계산이 끝난다는 것이다. 따라서 재귀는 최고 자릿수 + 1 까지만 해주면 된다. 따라서 문제에서 주어지는 최대값만 체크하면 되겠다.