C++で次に近い時刻を求めるアルゴリズム

問題概要

「HH:MM」形式で表された時刻が与えられます。このとき、現在の時刻に含まれている数字だけを再利用して、次に近い時刻を生成するのが課題です。各数字は何度でも繰り返し使用できます。

例えば、入力が「19:34」の場合、出力は「19:39」になります。数字 1・9・3・4 のみを使って作れる時刻の中で、最も近い未来の時刻が 19:39 だからです。「19:33」も同じ数字で作れますが、これは翌日の 19:33 を意味するため、実際には 23時間59分後の時刻になってしまいます。

解法のアプローチ

この問題は、あり得る時刻をすべて試す総当たり(ブルートフォース)法で効率よく解けます。手順は以下の通りです。

• eval() 関数を定義する: 引数 x を受け取り、前半2桁を「時」、後半2桁を「分」として整数に変換し、「時 × 60 + 分」で表される合計分数を返します。
• 変数の初期化: 結果を格納する ret と作業用の一時文字列 temp を空文字列に、最小時間差 diff は INT_MAX(無限大相当)で初期化します。
• 使用できる数字を抽出: 入力時刻 t からコロンを除いた4文字(t[0]、t[1]、t[3]、t[4])を配列 time に格納します。
• 元の時刻の文字列 src を作成: 配列 time の内容を連結して、比較用の基準文字列を作ります。
• 4重ループで全組み合わせを生成: i、j、k、l の4重ループにより、時2桁(temp1)と分2桁(temp2)のすべての組み合わせを試します。
• 妥当性チェック: temp1 が 23 より大きい、または temp2 が 59 より大きい場合は不正な時刻なのでスキップします。
• 同一時刻の除外: 生成した時刻が元の時刻 src と一致する場合もスキップします。
• 時間差の計算: 新しい時刻と元の時刻の差(分)を求めます。差が負になる場合は、1日分の 1440 分(60 × 24)を加算して、日付をまたぐ差に補正します。
• 最小値の更新: 計算した差 newDiff が現在の最小値 diff より小さければ、diff と答え ret を更新します。
• 結果の返却: ループ終了後、ret が空文字列のままなら元の時刻 t をそのまま返し、そうでなければ ret を返します。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int eval(string x){
        string a = to_string(x[0]);
        a += x[1];
        string b = to_string(x[2]);
        b += x[3];
        return stoi(a) * 60 + stoi(b);
    }
    string nextClosestTime(string t) {
        string ret = "";
        string temp = "";
        int diff = INT_MAX;
        vector<char> time;
        time.push_back(t[0]);
        time.push_back(t[1]);
        time.push_back(t[3]);
        time.push_back(t[4]);
        int n = time.size();
        string src = "";
        string temp1 = "";
        string temp2 = "";
        for (int i = 0; i < n; i++)
            src += time[i];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    for (int l = 0; l < n; l++) {
                        temp1 = time[i];
                        temp1 += time[j];
                        temp2 = time[k];
                        temp2 += time[l];
                        if (stoi(temp1) > 23 || stoi(temp2) > 59)
                            continue;
                        temp = temp1 + temp2;
                        if (temp == src)
                            continue;
                        int newDiff = eval(temp) - eval(src);
                        if (newDiff < 0)
                            newDiff += (60 * 24);
                        if (newDiff < diff) {
                            diff = newDiff;
                            ret = temp1 + ":" + temp2;
                        }
                    }
                }
            }
        }
        return ret.size() == 0 ? t : ret;
    }
};
main(){
    Solution ob;
    cout<<(ob.nextClosestTime("19:34"));
}

入力

"19:34"

出力

19:39

計算量の目安

使用できる数字は最大4種類なので、生成する組み合わせの総数は高々 4⁴ = 256 通りです。したがって、この総当たり法でも十分高速に動作し、計算量は O(n⁴)(n は数字の種類数)に収まります。また、翌日への日付またぎを 1440 分の加算で処理している点が、正しく「次に近い時刻」を求めるポイントです。