Pythonで隣接する桁が同じにならない最小の数を生成するプログラム

文字列 s が与えられ、使用できる文字は「1」「2」「3」「?」の4種類とします。「?」の位置には「1」「2」「3」のいずれかを自由に置くことができます。このとき、隣接する2つの桁が同じ数字にならないという条件を満たす中で、作成可能な最小の数を求めるのが本記事の目的です。

問題例

たとえば、入力が s = "2??3?" の場合、出力は 21231 となります。各「?」を左から順に埋めていき、隣接する桁同士が一致しないように最小の数字を選ぶことで、この結果が得られます。

解法のアプローチ

この問題は貪欲法（グリーディー法）で解くことができます。文字列を左から順に走査し、「?」に遭遇するたびに、その位置の前後の数字を確認しながら条件を満たす最小の数字を割り当てていきます。

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

• インデックス i = 0 から走査を開始し、文字列をリストに変換します。
• 文字列の長さが2未満の場合、要素が「?」であれば「1」を返します。
• 各位置について「?」だった場合、次のように処理します。
  • 先頭（i = 0）の場合：右隣が「1」でなければ「1」を、そうでなければ「2」を設定します。
  • 中間（0 < i <= 長さ-2）の場合：左隣の値に応じて判定します。
    • 左隣が「1」：右隣が「2」なら「3」、それ以外は「2」。
    • 左隣が「2」：右隣が「1」なら「3」、それ以外は「1」。
    • 左隣が「3」：右隣が「1」なら「2」、それ以外は「1」。
  • 末尾の場合：左隣が「1」でなければ「1」を、そうでなければ「2」を設定します。
• すべての「?」を埋めたら、リストを結合して文字列として返します。

実装例

以下にPythonでの実装例を示します。

def solve(s):
    i = 0
    s = list(s)
    if len(s) < 2:
        if s[i] == "?":
            return "1"
    while i < len(s):
        if s[i] == "?":
            if i == 0:
                s[i] = "1" if s[i + 1] != "1" else "2"
            elif i > 0 and i <= len(s) - 2:
                if s[i - 1] == "1":
                    if s[i + 1] == "2":
                        s[i] = "3"
                    else:
                        s[i] = "2"
                elif s[i - 1] == "2":
                    if s[i + 1] == "1":
                        s[i] = "3"
                    else:
                        s[i] = "1"
                elif s[i - 1] == "3":
                    if s[i + 1] == "1":
                        s[i] = "2"
                    else:
                        s[i] = "1"
            else:
                s[i] = "1" if s[i - 1] != "1" else "2"
        i += 1
    return "".join(s)

s = "2??3?"
print(solve(s))

入力

"2??3?"

出力

21231

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、文字列をリストとして保持するため空間計算量も O(n) となります。非常に効率的で、長い入力に対しても高速に動作します。