9009는 아주 특별한 성질을 지닌 숫자입니다. 두 개의 2자리 숫자인 91과 99를 곱하면 9009가 되는데, 이것이 바로 두 자리 숫자끼리의 곱으로 만들 수 있는 가장 큰 회문수(palindrome)이기 때문입니다. 회문수란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 의미합니다.
이번 문제에서 작성해야 할 것은 자릿수 n을 인수로 받아, 두 개의 n자리 숫자를 곱하여 만들 수 있는 가장 큰 회문수를 찾아 반환하는 JavaScript 함수입니다. 예를 들어 n이 3이라면, 세 자리 숫자 두 개의 곱으로 만들 수 있는 가장 큰 회문수를 구해야 합니다.
알고리즘 접근 방법
모든 곱의 조합을 일일이 계산하는 것은 매우 비효율적입니다. 대신 다음과 같은 방식으로 문제를 해결할 수 있습니다.
- 범위 설정: n자리 숫자의 하한은 max(예: n=3이면 99), 상한은 sup(예: 999)입니다. 따라서 곱의 결과는 항상 max×max 이상, sup×sup 이하 범위 안에 존재합니다.
- 큰 수부터 탐색: sup×sup부터 max×max까지 1씩 감소시키며 각 수가 회문수인지 검사합니다.
- 약수 검증: 어떤 수가 회문수일 때, 그 수를 sup부터 제곱근(√n)까지의 값으로 나누어 나누어떨어지고 몫이 max보다 크다면, 두 약수가 모두 n자리 숫자라는 의미입니다. 이 경우 그 회문수가 정답입니다.
내림차순으로 탐색하기 때문에 조건을 만족하는 첫 번째 회문수가 곧 가장 큰 회문수가 됩니다.
예제 코드
다음은 전체 구현 코드입니다 −
const largestPalindromic = num => {
let i, n, m, d, max, sup, limit, number = 0;
for (i = 1; i < num; i += 1) {
number = 10 * number + 9;
};
max = number;
sup = 10 * number + 9;
const isPalindromic = n => {
let p = 0, q = n, r;
while (n > 0) {
r = n % 10;
p = 10 * p + r;
n = Math.floor(n / 10);
};
return p === q;
};
for (n = sup * sup, m = max * max; n > m; n -= 1) {
if (isPalindromic(n)) {
limit = Math.ceil(Math.sqrt(n));
d = sup;
while (d >= limit) {
if (n % d === 0 && n / d > max) {
return n;
}
d -= 1;
}
}
};
}
console.log(largestPalindromic(3));
출력 결과
위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다 −
906609
코드 상세 설명
- number 생성 루프: num−1번 반복하면서 9를 이어 붙여 (num−1)자리 숫자를 만듭니다. num이 3이면 number는 99가 됩니다.
- max와 sup: max는 n자리 숫자의 하한(99), sup은 n자리 숫자의 상한(999)을 나타냅니다.
- isPalindromic 함수: 숫자를 한 자리씩 분리해 뒤집은 뒤 원래 수와 비교하여 회문 여부를 판별합니다.
- 외부 루프: sup²부터 max²까지 값을 감소시키며 회문수를 찾습니다.
- 내부 루프: 회문수 n을 sup부터 √n까지의 값으로 나누어, 나누어떨어지고 몫이 max보다 클 때(즉, 두 약수가 모두 n자리 숫자일 때) 정답을 반환합니다.
실제로 906609는 913 × 993의 결과값으로, 세 자리 숫자 두 개의 곱으로 만들 수 있는 가장 큰 회문수입니다.