JavaScript로 딱 한 번의 스왑만으로 만들 수 있는 최댓값 구하기

문제 소개

숫자를 첫 번째이자 유일한 인수로 받아 처리하는 JavaScript 함수를 작성해야 합니다.

함수가 해야 할 일은 숫자의 두 자릿수를 최대 한 번 교환(swap)하여 만들 수 있는 가장 큰 수를 반환하는 것입니다. 만약 주어진 숫자가 이미 가능한 최댓값이라면, 해당 숫자를 그대로 반환하면 됩니다.

예시

입력 숫자가 다음과 같다면,

const num = 1625;

출력은 다음과 같아야 합니다.

const output = 6125;

첫째 자리의 1과 둘째 자리의 6을 서로 교환하면 되는데, 이것이 단 한 번의 스왑으로 얻을 수 있는 가장 큰 수입니다.

해결 접근 방법

이 문제의 핵심 아이디어는 다음과 같습니다.

숫자를 구성하는 자릿수 중 최댓값(max)을 찾습니다.
그 최댓값이 등장하는 위치 중 가장 뒤쪽 인덱스(lastIndexOf)를 구합니다.
앞쪽부터 탐색하면서 최댓값보다 작은 자릿수를 발견하면, 그 자릿수와 최댓값을 교환합니다.
교환이 필요 없는 경우라면 원래 숫자를 그대로 반환합니다.

최댓값이 여러 번 등장할 때는 가장 뒤쪽에 있는 것을 선택하는 것이 유리합니다. 그래야 상대적으로 작은 자릿수를 최대한 높은 자리로 끌어올려 더 큰 수를 만들 수 있기 때문입니다.

구현 코드

const num = 1625;

// 숫자의 모든 자릿수 중 최댓값을 재귀적으로 찾는 함수
const findMaximumDigit = (num, max = 0) => {
   if(!num){
      return max;
   };
   return findMaximumDigit(Math.floor(num / 10), Math.max(max, num % 10));
};

// 최대 한 번의 스왑으로 만들 수 있는 최댓값을 반환하는 함수
const makeOneSwap = (num = 1) => {
   let i = 0;
   const max = findMaximumDigit(num);
   const numStr = String(num);
   const numArr = numStr.split('');
   // 최댓값이 나타나는 가장 뒤쪽 인덱스
   const maxIndex = numStr.lastIndexOf('' + max);
   while(i < maxIndex){
      if(+numStr[i] < max){
         let temp = numArr[i];
         numArr[i] = numArr[maxIndex];
         numArr[maxIndex] = temp;
         break;
      };
      i++;
   };
   return +(numArr.join(''));
};

console.log(makeOneSwap(num));

코드 설명

findMaximumDigit: 재귀 호출을 통해 모든 자릿수를 확인하며 최댓값을 찾습니다. num % 10으로 마지막 자릿수를 꺼내고, Math.floor(num / 10)으로 자릿수를 하나씩 줄여 나갑니다.
makeOneSwap: 숫자를 문자열로 변환한 뒤 배열로 만들고, 최댓값의 마지막 위치(maxIndex)를 찾습니다. 이후 앞쪽에서부터 최댓값보다 작은 자릿수를 찾으면 두 값을 교환하고 즉시 반복을 종료합니다.
마지막에는 배열을 다시 문자열로 합친 후 단항 덧셈 연산자(+)로 숫자로 변환하여 반환합니다.

이 알고리즘의 시간 복잡도는 자릿수에 비례하는 O(d)로 매우 효율적입니다.

출력 결과

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