Pythonで時刻の数字を再利用して最も近い次の時刻を見つけるプログラム

「hh:mm」形式の24時間表記の時刻文字列が与えられたとき、その文字列に含まれる数字を再利用して作ることができる、最も近い次の時刻を求める問題を考えます。ここで重要なのは、与えられた文字列内の各数字は何度でも再利用できるという点です。

例えば、入力が s = "03:15" の場合、出力は 03:30 となります。これは、与えられた数字（0、3、1、5）だけを使って作れる時刻の中で、元の時刻に最も近い次の時刻が 03:30 だからです。

解法のアプローチ

この問題は、バックトラッキング（探索の枝戻り法）を使って、使用可能な数字のすべての組み合わせを生成することで解けます。ただし、時刻として有効な範囲（時は00〜23、分は00〜59）に収まるよう、以下の制約を設けます。

• 時の1桁目は「2」以下であること
• 時の1桁目が「2」の場合、2桁目は「3」以下であること
• 分の1桁目は「5」以下であること

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

• use := 与えられた時刻文字列から取り出した4つの数字（時2桁・分2桁）のリスト
• possible := 作成可能な時刻を格納するための空の集合（set）
• backtrack() 関数を定義する。引数として現在の組み合わせ path を受け取る
• path の長さが4になったら、最初の2桁 + ":" + 後ろの2桁を連結した文字列を possible に追加して return する
• use 内の各数字 p について、上記の制約条件をすべて満たす場合は backtrack(path + p) を再帰的に呼び出す
• メイン処理では、backtrack("") を呼び出して全組み合わせを生成した後、possible をリスト化してソートする
• ソート済みリストの中から入力時刻 s を探し、その次の要素（possible[i + 1]）を返す
• s がリストの末尾にある場合は、一巡して最小の時刻 possible[0] を返す

なお、時刻は一日で循環するため、入力時刻より後の時刻が存在しない場合は、翌日の最初の時刻（リストの先頭）が答えになります。

実装例

以下のPythonコードを見ると、処理の流れがより理解しやすくなります。

class Solution:
    def solve(self, s):
        use = [s[0], s[1], s[3], s[4]]
        possible = set()

        def backtrack(path):
            nonlocal possible, use
            if len(path) == 4:
                possible.add(path[:2] + ":" + path[2:])
                return
            for p in use:
                if (not (len(path) == 0 and p > "2")
                    and not (path == "2" and p > "3")
                    and not (len(path) == 2 and p > "5")):
                    backtrack(path + p)

        backtrack("")
        possible = list(possible)
        possible.sort()
        for i in range(len(possible) - 1):
            if possible[i] == s:
                return possible[i + 1]
        return possible[0]

ob = Solution()
s = "03:15"
print(ob.solve(s))

入力

"03:15"

出力

03:30

このように、バックトラッキングによって有効な時刻をすべて列挙し、ソート後に次の時刻を取得するだけで、シンプルかつ確実に答えを求められます。計算量は最大でも4桁の組み合わせ程度に抑えられるため、実用上十分な速度で動作します。