Pythonで1桁を「3」に変更して作れる最大の数を求める方法

問題概要

1、2、3 のみで構成された整数 n が与えられるとします。ここで、どれか1桁を「3」に変更できる場合、作成できる最大の数を求めます。

例えば、入力が 11332 の場合、先頭の「1」を「3」に変更することで、出力は 31332 となります。

解法のアプローチ

この問題は貪欲法（グリーディ法）で効率よく解くことができます。数を最大化するためには、位取りの重みが最も大きい左側（上位）の桁から順に確認し、最初に見つかった「3」以外の数字を「3」に変更するのが最適です。

具体的な手順は以下の通りです。

• n を文字列化し、各桁を要素とするリスト li を作成します。

• x を 0 からリストの長さ - 1 まで順番にループさせます。

• li[x] が '3' でない場合は、li[x] を '3' に変更し、その時点で各桁を連結して数値として返します。

• すべての桁がすでに '3' である場合は、元の n をそのまま返します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
    def solve(self, n):
        li = list(str(n))
        for x in range(len(li)):
            if li[x] != '3':
                li[x] = '3'
                return int(''.join(li))
        return n
ob = Solution()
print(ob.solve(11332))

入力

11332

出力

31332

計算量の評価

• 時間計算量：O(d) ― d は整数 n の桁数です。最悪でも全桁を一度走査するだけで済みます。

• 空間計算量：O(d) ― 各桁を格納するリストが必要です。

まとめ

このように、左端から「3」以外の最初の桁を探して置き換えるというシンプルな貪欲戦略により、たった1回の走査で最大の数を求められます。桁の位置（位）が大きいほど数への影響も大きいため、「できるだけ左の桁を大きくする」ことが最適解につながる点がポイントです。