자바스크립트에서 숫자 한 자리만 옮겨 만들 수 있는 가장 작은 수 구하기

문제 이해하기

양의 정수 n이 주어졌을 때, 단 한 번의 연산만 허용하여 만들 수 있는 가장 작은 수를 구하는 자바스크립트 함수를 작성해야 합니다. 여기서 허용되는 연산은 다음과 같습니다.

숫자의 특정 자리를 하나 선택해 그 자리의 숫자를 제거한 뒤, 같은 위치 또는 다른 위치에 다시 삽입하는 것입니다. 이 연산을 통해 얻을 수 있는 가장 작은 수가 곧 정답이 됩니다.

예를 들어 354166이 입력으로 주어지면, 네 번째 자리의 1을 맨 앞으로 옮겨 135466을 만들 수 있습니다.

풀이 코드

다음은 위 문제를 해결하는 자바스크립트 코드입니다.

const num = 354166;
const smallestShuffle = (num) => {
    const arr = String(num).split('');
    const { ind } = arr.reduce((acc, val, index) => {
        let { value, ind } = acc;
        if(value > val){
            value = val;
            ind = index;
        };
        return { value, ind };
    }, { value: Infinity, ind: -1 });
    const [item] = arr.splice(ind, 1);
    arr.unshift(item);
    return Number(arr.join(''));
};
console.log(smallestShuffle(num));

실행 결과

콘솔에는 다음과 같이 출력됩니다.

135466

코드 동작 원리

이 풀이는 그리디(greedy) 알고리즘에 기반하며, 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1. 자릿수 분리: String()으로 숫자를 문자열로 변환한 뒤 split('')으로 각 자릿수를 요소로 하는 배열을 만듭니다.
2. 최소 자릿수 탐색: reduce()로 배열을 순회하며 가장 작은 숫자와 그 인덱스를 추적합니다. 초기값을 Infinity로 설정해 첫 번째 자릿수와도 비교할 수 있도록 합니다.
3. 숫자 이동: splice()로 최소 자릿수를 꺼낸 후 unshift()로 배열의 맨 앞에 삽입합니다.
4. 결과 반환: join('')으로 배열을 다시 문자열로 합친 뒤 Number()로 변환하여 반환합니다.

가장 작은 자릿수를 맨 앞으로 보내면 나머지 자릿수의 상대적인 순서는 유지되면서 전체 값이 최소화됩니다. 만약 최소 자릿수가 이미 맨 앞에 있다면 원래 숫자가 그대로 반환됩니다. 이 알고리즘의 시간 복잡도는 자릿수 길이에 비례하는 O(n)으로 매우 효율적입니다.