문제 소개
숫자 num을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수의 목표는 입력받은 숫자의 자릿수를 모두 그대로 사용하면서(순서만 재배열하여), 입력값보다 바로 다음으로 큰 수를 찾아 반환하는 것입니다.
조건을 만족하는 수가 존재하지 않는다면 함수는 -1을 반환해야 합니다.
입력 및 출력 예시
const num = 5656;
위 입력에 대한 기대 출력은 다음과 같습니다.
const output = 5665;
출력 설명
5665는 5656의 자릿수(5, 6, 5, 6)를 모두 그대로 사용하면서 5656보다 큰 수 중 가장 작은 값이기 때문입니다. 즉, 5665 다음으로 이 조건을 만족하는 수는 존재하지 않습니다.
풀이 코드 (완전 탐색 방식)
const num = 5656;
const justBigger = (num) => {
const sorted = num => ('' + num).split('').sort((a, b) => b - a);
const max = +sorted(num).join('');
for (let i = num + 1; i <= max; i++) {
if (max === +sorted(i).join('')) {
return i;
}
}
return -1;
}
console.log(justBigger(num));
실행 결과
5665
코드 동작 원리
이 코드는 완전 탐색(brute force) 방식으로 동작합니다.
먼저 입력 숫자의 자릿수를 내림차순으로 정렬해 만들 수 있는 가장 큰 수(max)를 구합니다. 그다음 num + 1부터 max까지 한 숫자씩 검사하면서, 자릿수를 내림차순으로 정렬했을 때 max와 동일해지는 첫 번째 수를 찾습니다. 내림차순 정렬 결과가 같다는 것은 두 수가 정확히 같은 자릿수 집합을 공유한다는 의미이므로, 가장 먼저 발견되는 수가 곧 '바로 다음으로 큰 수'입니다.
끝까지 찾지 못하면 -1을 반환합니다.
이 방식의 단점
직관적이지만, 숫자의 길이가 길어지면 num과 max 사이의 모든 수를 일일이 검사해야 하므로 성능이 크게 저하될 수 있습니다.
개선된 풀이: 다음 순열(Next Permutation) 알고리즘
자릿수 배열에 다음 순열 알고리즘을 적용하면 반복 검사 없이 한 번의 순회로 답을 구할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- 피벗 찾기: 뒤에서부터 앞으로 탐색하며 처음으로 digits[i] < digits[i + 1]을 만족하는 위치 i를 찾습니다. 이 지점이 교환 기준점(피벗)입니다.
- 교환 대상 찾기: 피벗 오른쪽 구간에서 digits[i]보다 큰 수 중 가장 오른쪽에 있는 값을 찾습니다. 중복 자릿수가 있어도 안전하게 동작합니다.
- 교환: 피벗과 해당 값을 맞바꿉니다.
- 정렬: 피벗 뒤쪽 구간을 오름차순으로 만듭니다. 이 구간은 이미 내림차순 상태이므로 단순히 뒤집기만 하면 됩니다.
처음부터 끝까지 탐색해도 피벗이 존재하지 않는다면, 입력 숫자가 이미 만들 수 있는 가장 큰 수라는 뜻이므로 -1을 반환합니다.
const justBigger = (num) => {
const digits = String(num).split('');
// 1. 뒤에서부터 피벗(감소가 멈추는 지점) 찾기
let i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) {
i--;
}
// 피벗이 없으면 이미 최대값이므로 -1 반환
if (i < 0) return -1;
// 2. 피벗보다 큰 수 중 가장 오른쪽 값 찾기
let j = digits.length - 1;
while (digits[j] <= digits[i]) {
j--;
}
// 3. 교환
[digits[i], digits[j]] = [digits[j], digits[i]];
// 4. 피벗 뒤쪽 구간 뒤집기 (오름차순 정렬)
let left = i + 1;
let right = digits.length - 1;
while (left < right) {
[digits[left], digits[right]] = [digits[right], digits[left]];
left++;
right--;
}
return Number(digits.join(''));
};
console.log(justBigger(5656)); // 5665
console.log(justBigger(1234)); // 1243
console.log(justBigger(21)); // -1
복잡도 비교
완전 탐색 방식은 두 수의 차이만큼 반복해야 하므로 최악의 경우 매우 많은 연산이 필요합니다. 반면 다음 순열 알고리즘은 자릿수 개수 n에 대해 O(n) 시간 복잡도를 보장하므로, 숫자가 아무리 길어져도 항상 빠르게 답을 구할 수 있습니다.