Pythonで隠れた数字（?）を置き換えて最も遅い有効な時刻を求めるプログラム

問題の概要

文字列 s が「hh:mm」形式の時刻を表しているとします。ただし、一部の桁は隠されていて「?」で表されています。ここでは24時間制を扱い、有効な時刻は「00:00」〜「23:59」の範囲とします。隠された桁を適切な数字に置き換えることで得られる、最も遅い（最新の）有効な時刻を求めるのがこの問題の目的です。

たとえば入力が s = "1?:?5" の場合、出力は "13:55" となります。このアルゴリズムでは、時刻の上限となるテンプレート「23:59」をあらかじめ用意し、必要に応じて調整しながら、入力の各桁を先頭から順に処理していきます。すでに数字が指定されている桁はそのまま残し、「?」の部分にはテンプレート側の数字を採用します。

解法のステップ

• 結果を格納するための空のリスト ans を用意します。
• 時刻の上限テンプレート max_time を ['2','3',':','5','9']（＝ "23:59"）で初期化します。
• max_time[0] が '2' 未満の場合は、max_time[1] を '9' に更新します（十の位が1以下なら、一の位は9まで許容できるため）。
• '9' >= max_time[1] > '3' が成り立つ場合は、max_time[0] を '1' に更新します（一の位が4以上の場合、十の位は1に制限する必要があるため）。
• zip() で max_time と s をペアにしながら先頭から順に走査します。
  • s 側の文字が数字であれば、その数字を ans の末尾に追加します。
  • そうでない場合（「?」や「:」など）は、テンプレート側の文字 mx を ans の末尾に追加します。
• ans 内の文字を連結した文字列を返します。

Pythonでの実装例

理解を深めるために、次の実装を見てみましょう。

def solve(s):
    ans = []
    max_time = ['2','3',':','5','9']
    if max_time[0] < '2':
        max_time[1] = '9'
    if '9' >= max_time[1] > '3':
        max_time[0] = '1'
    for mx,digit in zip(max_time,s):
        if digit.isdigit():
            ans.append(digit)
        else:
            ans.append(mx)
    return ''.join(ans)

s= "1?:?5"
print(solve(s))

入力と出力

入力：

"1?:?5"

出力：

13:55

処理の流れ（"1?:?5" の場合）

• 1文字目：'1' は数字なのでそのまま採用 →「1」
• 2文字目：'?' は数字ではないため、テンプレートの '3' を採用 →「13」
• 3文字目：':' は区切り文字なのでそのまま →「13:」
• 4文字目：'?' は数字ではないため、テンプレートの '5' を採用 →「13:5」
• 5文字目：'5' は数字なのでそのまま採用 →「13:55」

計算量

時刻文字列の長さは常に5文字と固定されているため、処理は一度の走査で完了します。時間計算量・空間計算量はいずれも O(1) です。