C++で3の倍数の最大値を求めるアルゴリズムを解説

数字の配列が与えられたとき、その中から任意の個数の数字を選び、好きな順序で連結して作ることができる「3の倍数」の最大値を求めます。答えは非常に大きな数になる可能性があるため、文字列として返します。条件を満たす組み合わせが存在しない場合は、空文字列を返します。

たとえば、入力が [7, 2, 8] の場合、出力は 87 になります。

解法のポイント

この問題を解く鍵となるのは、「ある整数が3の倍数であること」と「その各位の数字の総和が3の倍数であること」が同値であるという有名な性質です。これを利用すると、次のような戦略が立てられます。

• 3行からなる2次元配列 d を定義する(d[x mod 3] には「3で割った余りが x」に相当する数字を格納)

• 配列 digits を降順にソートする

• sum := 0 で初期化する

• i := 0 から digits のサイズ未満まで、i を1ずつ増やしながら繰り返す:

  • x := digits[i]

  • d[x mod 3] の末尾に digits[i] を追加する

  • sum := sum + x とし、続けて sum := sum mod 3 とする

• sum が 0 以外の場合:

  • d[sum] が空の場合:

    • rem := 3 - sum とする

    • d[rem] のサイズが 2 未満であれば、空文字列を返す

    • d[rem] の末尾から要素を2つ削除する

  • それ以外の場合:

    • d[sum] の末尾から要素を1つ削除する

• ret := 空文字列 で初期化する

• i := 0 から 2 まで繰り返し、各 d[i] のすべての要素を文字列として ret に連結する

• ret を降順にソートする

• ret のサイズが 0 より大きく、先頭文字が '0' である場合は "0" を返す

• ret を返す

ここで重要なのは、sum が 1 のときは「余り 1 の数字を1つ」または「余り 2 の数字を2つ」取り除けばよく、sum が 2 のときも同様の発想で対応できるという点です。あらかじめ降順にソートしておけば、削除対象は常に配列の末尾(最も小さい数字)になるため、処理がシンプルになります。

それでは、以下の実装例を見て理解を深めましょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string largestMultipleOfThree(vector<int>& digits) {
        vector<vector<int>> d(3);
        sort(digits.begin(), digits.end(), greater<int>());
        int sum = 0;
        for (int i = 0; i < digits.size(); i++) {
            int x = digits[i];
            d[x % 3].push_back(digits[i]);
            sum += x;
            sum %= 3;
        }
        if (sum) {
            if (!d[sum].size()) {
                int rem = 3 - sum;
                if (d[rem].size() < 2)
                return "";
                d[rem].pop_back();
                d[rem].pop_back();
            }
            else {
                d[sum].pop_back();
            }
        }
        string ret = "";
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < d[i].size(); j++) {
                ret += to_string(d[i][j]);
            }
        }
        sort(ret.begin(), ret.end(), greater<int>());
        if (ret.size() && ret[0] == '0')
        return "0";
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {7,2,8};
    cout << (ob.largestMultipleOfThree(v));
}

入力

{7,2,8}

出力

87