Pythonで数値の任意の位置に5を挿入して最大値を求める方法

整数 n が与えられたとき、数字「5」を任意の位置に1つ挿入することで得られる最大の数を求める問題を考えてみましょう。

例えば、n = 834 の場合、出力は 8534 になります。これは「8」と「3」の間に「5」を挿入した結果です。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• n が正の数の場合:
  • s := n を文字列に変換
  • k := 空の文字列
  • c := False(挿入済みフラグ)
  • s の各文字 i について繰り返し処理を行う:
    • i が「5」未満かつ c が False の場合:
      • k := k + "5" + i
      • c := True
    • それ以外の場合:
      • k := k + i
  • k を整数として返す
• n が負の数の場合:
  • k := 空の文字列
  • s := |n|(絶対値)を文字列に変換
  • c := False
  • s の各文字 i について繰り返し処理を行う:
    • i が「5」より大きいかつ c が False の場合:
      • k := k + "5" + i
      • c := True
    • それ以外の場合:
      • k := k + i
  • c が最後まで False のままの場合(挿入されなかった場合):
    • k := k + "5"(末尾に挿入)
• -k を返す

なぜこのアルゴリズムが機能するのか

正の数の場合、上の桁ほど大きな数字を配置する方が数は大きくなります。そのため、「5」より小さい最初の数字の直前に「5」を挿入すれば、以降の数字が一つずつ右にずれ、結果として最大の数が得られます。

一方、負の数の場合は逆の発想が必要です。負の数では絶対値が小さいほど実際の値は大きくなるため、「5」より大きい最初の数字の直前に挿入します。もし該当する数字がなければ、末尾に「5」を付ければ絶対値は最小になり、これが最適です。

実装例

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

def solve(n):
   if n > 0:
      s = str(n)
      k = ""
      c = False
      for i in s:
         if int(i) < 5 and c == False:
            k += "5" + i
            c = True
         else:
            k += i
      return int(k)
   else:
      k = ""
      s = str(abs(n))
      c = False
      for i in s:
         if int(i) > 5 and c == False:
            k += "5" + i
            c = True
         else:
            k += i
      if not c:
          k += "5"
      return int("-" + k)

n = 834
print(solve(n))

入力

834

出力

8534

計算量について

このアルゴリズムの時間計算量は O(d) です。ここで d は数値 n の桁数を表します。文字列を一度だけ走査すればよいため、非常に効率的な手法といえます。