Project Euler 004を解いてみる。「最大の回文積」

#Project Euler 004
004

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

->次の問題

考え方

回文数の判定のため、数字の並びを反転する関数を考えました。
10で割った余りを利用して一の位から順番に数字を抜き出し、resultに足します。次のループでresultに10をかけて桁を左にずらしています。
アルゴリズムとして割とスッキリできたと思います。

euler004.py

def number_reverse(n: int) -> int:
    """
    正の整数nを反転させた整数を返す。
    n=1234 -> result=4321
    :param n: int
    :return: int
    """
    result = 0
    while n > 0:
        result *= 10
        result += n % 10
        n = n // 10
    return result

###追記
コメント頂きましたので修正いたしました。strへの型変換を行うと速度が遅くなるかなと思っていたのですが、上のアルゴリズムとstrに型変換して[::-1]で逆順を比較したところ、型変換のほうが2.5倍くらい早いという結果になりました。
おそらくwhile内の計算量 > 型変換ということなのでしょう。

def str_main():
    n = 10 ** 3 #3桁を対象
    answer = 0
    for i in reversed(range(n // 10, n)): #iは999~100の順で生成
        for j in reversed(range(i, n)): #jは999~iの順で生成
            temp = i * j
            if temp < answer: #最大値を求めるのでi*jがansより小さいなら以降の判定は不要 
                break
            str_temp = str(temp) #乗算した結果を文字列[str]に変換
            if str_temp == str_temp[::-1]: #スライス機能を使い、[::-1]で反転した文字列を取得
                ans = temp
        if i * (n - 1) < answer: # iはどんどん小さくなるので、i*jの取りうる最大値(=i*999)よりanswerが大きければ以降の処理は不要。
            break
    print(answer)


if __name__ == '__main__':
    str_main()

コード

内包表記で100~999のそれぞれを乗算したsetを作成しlistに変換。setから変換することで重複を削除しています。i * jではiとjは入れ替え可能なのでi ≦ jとしています。
sort(reverse=True)で逆順にしてforでループを回しています。
かなり無駄な数のリストを作ってしまっているのでこの部分をどうにかスッキリしたいところですが、
良い案が思いつかないので、そのまま回しています。

euler004.py

def main():
    n = 10 ** 3 # 3桁を対象
    num_list = list(set(i * j
                        for i in range(n // 10, n)
                        for j in range(i, n)))
    num_list.sort(reverse=True)
    for n in num_list:
        if n == number_reverse(n):
            print(n)
            break


def number_reverse(n: int) -> int:
    """
    正の整数nを反転させた整数を返す。
    1234->4321
    :param n: int
    :return: int
    """
    result = 0
    while n > 0:
        result *= 10
        result += n % 10
        n = n // 10
    return result


if __name__ == '__main__':
    main()

結果 906609 main処理時間: 0.16022491455078125 sec.