라딕스 정렬

십진수에서 특정 자릿수를 추출하는 방법

출처:chatGpt

x를 10의 a승으로 나눈 몫을 가져오는 것은 추출하고자 하는 자릿수가 일의 자리로 이동하도록 하는 과정이다.

"123"에서 1번째 자릿수인 1을 일의 자리로 취하기 위해서 10의 2승으로 나눈 몫을 가져온다.

1이 위치한 곳은 100(백) 단위기 때문에 10의 2승인 100으로 나눠야지 1을 일의 자리로 이동시킬 수 있다.

주어진 숫자가 십진수이기 때문에 10으로 나눈 나머지는 0~9 사이의 값이 나온다.

왜냐하면 십으로 나누면 십 이상의 자릿수는 모두 사라지기 때문에 0~9 사이의 일의 자리만 나머지가 발생함

코드

import java.util.*;

public class Main2 {    

    // 알고리즘을 왜? 풀어야지에 대한 의문이 계속해서 생김 왜 그럴까?     
    static int n = 15;
    static int[] arr = {2, 312, 1, 10, 5};
    static int d = 3; // 자릿수의 최댓값
    static int[] p10 = new int[3]; // 10의 지수를 저장할 배열

    // 10개의 ArrayList<Integer>로 구성된 배열 선언
    static ArrayList<Integer>[] list = new ArrayList[10];

    public static int digitNum(int x, int a) {
        return (x / p10[a]) % 10;
    }

    public static void main(String[] args) {        
        p10[0] = 1;
        // 지수 승을 저장 
        // [0] - 1의 자리, [1] - 십의 자리
        for(int i=1;i<d;i++) p10[i] = p10[i-1] * 10; 

        // ArrayList 초기화(자바의 경우 명시적인 초기화 필수, C++은 X)
        for(int i=0; i<10; i++) list[i] = new ArrayList<Integer>();

        // 1의 자리부터 수가 저장된 최대 자릿수까지 for문을 돔
        // 1의 자리 기준으로 정렬 -> 십의 자리 기준으로 정렬 ... 최대 자릿수까지 정렬
        for(int i=0;i<d;i++) {
            for(int j=0;j<10;j++) list[j].clear();
            for(int j=0;j<arr.length;j++) {
                list[digitNum(arr[j], i)].add(arr[j]);
            }
            // 정렬된 리스트를 다시 arr에 합치기
            int index = 0;
            for(int j=0; j<10; j++) {
                for(int num : list[j]) {
                    arr[index++] = num;
                }
            }
        }

        // 정렬 결과 출력
        for(int num : arr) {
            System.out.print(num + " ");
        }
    }
}

ArrayList 배열 형태 구조

출처 : chatgpt

 

각각의 배열안에 ArrayList 객체가 있는 것이 아니라 각 인덱스는 ArrayList 객체를 참조할 수 있는 변수를 가지고 있다. 

[0]째 인덱스는 크기가 3인 3개의 동적 배열을 가지고 있다.