C++で4桁の数字から作れる最大の24時間制の時刻を求める方法

問題概要

4つの数字が格納された配列が与えられます。これらの数字をすべて使い、作成できる最大の24時間制の時刻を求めてください。最も早い時刻は 00:00、最も遅い時刻は 23:59 です。00:00 を基準として、深夜0時からの経過時間が長いほど「大きい」時刻とみなします。答えは必ず5文字の文字列("HH:MM" 形式)として返し、有効な時刻を構成できない場合は空文字列を返します。

たとえば、入力が [1, 2, 3, 4] の場合、出力は "23:41" になります。

解法のアプローチ

この問題は、深さ優先探索(DFS)とバックトラッキングを組み合わせ、4桁の数字の全順列を試すことで解けます。具体的な手順は以下の通りです。

• isValid() 関数の定義： 文字列 a を引数に取り、それが有効な時刻を表しているかを判定します。
  • a[0](時の十の位)が '2' より大きい場合は false を返す
  • a[0] が '2' であり、かつ a[1](時の一の位)が '3' より大きい場合は false を返す(時は 00〜23 の範囲のみ有効)
  • a[3](分の十の位)が '5' より大きい場合は false を返す(分は 00〜59 の範囲のみ有効)
  • 上記の条件をすべて満たせば true を返す
• dfs() 関数の定義： 配列 A、結果を格納する res、現在構築中の文字列 cur を引数に取ります。
  • cur の長さが 5 になったら、isValid(cur) が true かつ cur が res より大きい場合に res を更新し、return する
  • i を 0 から 3 までループし、A[i] が未使用(-1 以外)であれば次の処理を行う
    • A[i] の値を一時変数 tmp に保存し、cur の末尾にその数字('0' を加えて文字に変換)を追加する
    • cur の長さが 2 になったタイミングで ':' を追加する("HH:" の形を作る)
    • A[i] を -1 にして使用済みマークを付け、dfs を再帰呼び出しする
    • 再帰から戻ったら A[i] を tmp で元に戻し、cur の末尾の文字を削除する(バックトラッキング)。このとき cur の長さが 2 になっていれば ':' も一緒に削除する
• メイン処理： res と tmp を空文字列で初期化し、dfs(A, res, tmp) を呼び出した後、res を返します。

C++ 実装例

理解を深めるために、以下の実装例をご覧ください。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void dfs(vector<int>& A, string& res, string& cur) {
        if (cur.size() == 5) {
            if (isValid(cur) && cur > res)
                res = cur;
            return;
        }
        for (int i = 0; i < 4; ++i) {
            if (A[i] != -1) {
                int tmp = A[i];
                cur += A[i] + '0';
                if (cur.size() == 2)
                    cur += ':';
                A[i] = -1;
                dfs(A, res, cur);
                A[i] = tmp;
                cur.pop_back();
                if (cur.size() == 2)
                    cur.pop_back();
            }
        }
    }

    bool isValid(const string a) {
        if (a[0] > '2')
            return false;
        if (a[0] == '2' && a[1] > '3')
            return false;
        if (a[3] > '5')
            return false;
        return true;
    }

    string largestTimeFromDigits(vector<int>& A) {
        string res = "", tmp = "";
        dfs(A, res, tmp);
        return res;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 2, 3, 4};
    cout << ob.largestTimeFromDigits(v);
    return 0;
}

入力

{1,2,3,4}

出力

23:41

補足：有効な時刻が存在しないケース

たとえば入力が {5,5,5,5} のような場合、どの順列でも時の十の位が '5' となり isValid() の判定に失敗するため、空文字列 "" が返されます。この挙動により、無効な入力に対しても安全に対応できます。

計算量

4桁の順列は最大 4! = 24 通りしか存在しないため、この問題の時間計算量は事実上 O(1)(定数時間)です。一般的に n 桁に拡張した場合は O(n!) となります。また、再帰の深さは最大 5 程度であるため、空間計算量も O(1) と非常に効率的です。