회문 곱

지침

주어진 범위에서 회문 곱을 찾아요.

회문 수는 숫자를 뒤집어도 그대로인 수를 말해요. 예를 들어 121은 회문 수지만 112는 아니에요.

주어진 숫자 범위에서, 그 범위 안의 두 수를 곱해 나온 회문 중 가장 큰 것과 가장 작은 것을 찾아요.

풀이는 범위 안에서 가장 큰 회문과 가장 작은 회문, 그리고 각각의 인수를 반환해야 해요. 가장 큰 회문이나 가장 작은 회문에 범위 안의 인수 쌍이 여러 개 있으면, 그 쌍을 모두 반환해요.

예제 1

범위 [1, 9]가 주어졌을 때(양 끝 포함)...

그리고 이 범위에서 나올 수 있는 모든 곱의 목록이 주어지면: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 15, 21, 24, 27, 20, 28, 32, 36, 25, 30, 35, 40, 45, 42, 48, 54, 49, 56, 63, 64, 72, 81]

회문 곱은 모두 한 자리 수예요 (이 경우에는): [1, 2, 3, 4, 5, 6, 7, 8, 9]

가장 작은 회문 곱은 1이에요. 인수는 (1, 1)이에요. 가장 큰 회문 곱은 9예요. 인수는 (1, 9)와 (3, 3)이에요.

예제 2

범위 [10, 99]가 주어졌을 때(양 끝 포함)...

가장 작은 회문 곱은 121이에요. 인수는 (11, 11)이에요. 가장 큰 회문 곱은 9009예요. 인수는 (91, 99)예요.

힌트

이 연습 문제를 풀려면 다음 두 함수를 구현해야 해요:

• largestPalindrome
• smallestPalindrome

두 함수는 인수의 하한과 상한을 받고, 회문과 그 회문을 만들 수 있는 인수 쌍들을 담은 (value, [(factor1, factor2)]) 쌍을 반환해요.

타입이 확실하지 않다면 제공된 시그니처를 그대로 사용해도 괜찮아요. 다만 그것 때문에 창의력을 제한할 필요는 없어요.

인수 목록에 중복이 있어도 괜찮고, 인수의 순서는 상관없어요.

작은 회문이나 큰 회문을 찾을 때는 조금 다른 알고리즘을 사용하는 것도 고려해 봐요.

---

출처

Project Euler의 Problem 4