JavaScript에서 문자열 메서드와 배열 없이 정수 자릿수 정렬하기

이번 글에서는 숫자 하나를 인자로 받아, 그 숫자의 자릿수를 재배열하여 만들 수 있는 가장 작은 수를 반환하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어 입력값이 다음과 같다면,

const num = 614532;

출력 결과는 아래와 같아야 합니다.

const output = 123456;

제약 조건

여기서 중요한 조건은 문자열(String) 메서드를 사용할 수 없고, 데이터를 저장하기 위해 배열도 사용할 수 없다는 점입니다. 즉, 순수한 산술 연산만으로 자릿수를 정렬해야 합니다.

해결 아이디어

핵심 접근 방식은 다음과 같습니다.

1. Math.floor(num / 10 ** e) % 10 연산을 통해 특정 위치(e번째)의 자릿수를 추출합니다.
2. 왼쪽 자릿수가 오른쪽 자릿수보다 크면 두 자릿수의 위치를 교환합니다.
3. 교환이 일어나면 처음부터 다시 검사하여 더 이상 교환이 필요 없을 때까지 반복합니다(버블 정렬과 유사한 방식).

구현 코드

const num = 614532;
const sortDigits = num => {
    // e번째 자릿수를 추출하는 헬퍼 함수
    const getDigit = e => Math.floor(num / 10 ** e) % 10;
    // 숫자의 최상위 자릿수 위치 계산
    const l = Math.ceil(Math.log10(num)) − 1;
    let e = l;
    while (e−−) {
        const left = getDigit(e + 1);
        const right = getDigit(e);
        // 왼쪽이 오른쪽보다 작거나 같으면 교환 불필요
        if (left <= right){
            continue;
        };
        // 두 자릿수를 교환
        num += (right − left) * 9 * 10 ** e;
        // 교환이 발생하면 처음부터 다시 검사
        e = l;
    };
    return num;
}
console.log(sortDigits(num));

코드 설명

getDigit 함수는 10의 거듭제곱으로 나눈 후 나머지 연산을 적용하여 원하는 자리의 숫자를 얻습니다. 예를 들어 e = 2일 때 614532 / 100 = 6145.32의 정수 부분인 6145에 10을 나눈 나머지 5, 즉 백의 자리 숫자 5를 얻게 됩니다.

두 자릿수를 교환하는 부분인 num += (right − left) * 9 * 10 ** e는 산술적 트릭입니다. 왼쪽 자릿수에서 오른쪽 자릿수를 빼고 그 차이를 적절한 자리 가중치에 곱해 더함으로써, 배열이나 문자열 변환 없이 숫자 자체에서 직접 자릿수를 맞바꾸는 효과를 냅니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

이처럼 문자열 메서드와 배열 없이도 반복적인 자릿수 비교와 산술 연산만으로 숫자의 자릿수를 오름차순으로 정렬할 수 있습니다.