Pythonで数値に5を挿入して最大の数を作るアルゴリズム

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

たとえば、入力が n = 826 の場合、「5」を挿入できる候補は「5826」「8526」「8256」「8265」の4通りあります。この中で最大となるのは 8526 であり、これが出力になります。

解法のアプローチ

この問題は、考えられるすべての挿入位置を試すシンプルな全探索で効率的に解くことができます。手順は以下の通りです。

• temp: 数値 n を文字列に変換したもの
• ans: 初期値として負の無限大(float('-inf'))を設定
• i を 0 から temp の長さまで順にループ処理する
  • cand: temp の先頭から i 文字目までの部分文字列 + 「5」+ i 文字目以降の部分文字列を連結したもの
  • i が 0 かつ temp[0] が「-」(負の数)の場合は、その反復をスキップする
  • ans: ans と cand を整数に変換した値のうち、大きい方を採用する
• ループ終了後、ans を返す

負の数を扱う際は、符号「-」の直前に「5」を挿入すると不正な文字列になってしまうため、i = 0 のケースを除外している点がポイントです。

実装例(Python)

class Solution:
   def solve(self, n):
      temp = str(n)
      ans = float('-inf')
      for i in range(len(temp) + 1):
         cand = temp[:i] + '5' + temp[i:]
         if i == 0 and temp[0] == '-':
            continue
         ans = max(ans, int(cand))
      return ans

ob = Solution()
print(ob.solve(826))

入力

826

出力

8526

まとめ

数値を一度文字列に変換し、可能なすべての位置に「5」を挿入した候補を生成してその最大値を取ることで、桁数を d としたとき O(d) 個の候補から答えを求められます。負の数への対応も、符号位置への挿入をスキップするだけで簡単に実現できる、非常にシンプルかつ実用的な手法です。