좋은 밑수(Good Base)란?
정수 num에 대해, k(k ≥ 2)진법으로 num을 표현했을 때 모든 자릿수가 전부 1이라면, 우리는 k를 num의 좋은 밑수(good base)라고 부릅니다.
예를 들어, 13을 3진법으로 나타내면 111이 됩니다. 따라서 3은 num = 13의 좋은 밑수입니다.
문제 정의
숫자를 나타내는 문자열 str을 유일한 인수로 받아, 해당 숫자의 가장 작은 좋은 밑수를 문자열 형태로 반환하는 자바스크립트 함수를 작성해야 합니다.
예를 들어, 함수에 다음과 같이 입력한다고 가정해 보겠습니다 −
const str = "4681";
그렇다면 출력은 다음과 같아야 합니다 −
const output = "8";
출력 설명
4681을 8진법으로 표현하면 11111이 되기 때문입니다.
예시 코드
이 문제를 해결하는 코드는 다음과 같습니다 −
const str = "4681";
const smallestGoodBase = (n = '1') => {
const N = BigInt(n), bigint2 = BigInt(2), bigint1 = BigInt(1), bigint0 = BigInt(0)
let maxLen = countLength(N, bigint2) // 밑수가 2일 때의 최대 자릿수
const findInHalf = (length, smaller = bigint2, bigger = N) => {
if (smaller > bigger){
return [false];
};
if (smaller == bigger) {
return [valueOf1s(smaller, length) == N, smaller]
};
let mid = (smaller + bigger) / bigint2;
let val = valueOf1s(mid, length);
if(val == N){
return [true, mid];
};
if (val > N){
return findInHalf(length, smaller, mid - bigint1);
};
return findInHalf(length, mid + bigint1, bigger);
};
for (let length = maxLen; length > 0; length--) {
let [found, base] = findInHalf(length);
if(found){
return '' + base;
}
};
return '' + (N - 1);
function valueOf1s(base, lengthOf1s) {
let t = bigint1
for (let i = 1; i < lengthOf1s; i++) {
t *= base
t += bigint1
}
return t
}
function countLength(N, base) {
let t = N, len = 0
while (t > bigint0) {
t /= base
len++
}
return len
}
};
console.log(smallestGoodBase(str));출력 결과
콘솔에 출력되는 결과는 다음과 같습니다 −
8
코드 동작 원리
이 알고리즘의 핵심 아이디어는 다음과 같습니다.
- 어떤 수 num이 k진법에서 길이가 m인 "111…1"로 표현된다면, num = 1 + k + k² + … + k^(m−1)이라는 등비수열의 합 공식이 성립합니다.
- 밑수 k가 작아질수록 자릿수 m은 길어지므로, 가장 작은 밑수를 찾으려면 자릿수가 가장 긴 경우부터 차례대로 탐색해야 합니다.
- 자바스크립트의 Number 타입은 2^53 − 1보다 큰 정수에서 정밀도를 잃기 때문에, 이 코드는 BigInt를 사용해 임의 크기의 정수를 정확하게 처리합니다.
- countLength 함수는 밑수가 2일 때의 최대 자릿수를 계산해 탐색 범위의 상한을 정하고, valueOf1s 함수는 주어진 밑수와 자릿수에 대해 1 + k + … + k^(m−1)의 실제 값을 계산합니다.
- findInHalf 함수는 이분 탐색(binary search)을 통해 각 자릿수 길이마다 조건을 만족하는 밑수가 존재하는지 효율적으로 확인합니다.
- 만약 모든 자릿수 길이에서 적절한 밑수를 찾지 못하더라도 답은 반드시 존재합니다. 어떤 수 N이든 (N − 1)진법에서는 항상 "11"로 표현되므로, 최종적으로 N − 1을 반환합니다.
이처럼 수학적 성질과 이분 탐색을 결합하면 매우 큰 수에 대해서도 빠르게 가장 작은 좋은 밑수를 구할 수 있습니다.