C++で数字の配列から作れる3の倍数の最大値を求める方法

問題の概要

さまざまな数字が格納された配列が与えられます。その中からいくつかの数字を選び、任意の順序で連結することで作成できる「3の倍数」の最大値を求めるのが課題です。答えは非常に大きな数になる可能性があるため、文字列として返します。答えが存在しない場合は空文字列を返してください。

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

解法のアプローチ

この問題は「3の倍数の性質」を利用することで効率的に解けます。ある整数が3の倍数であるための必要十分条件は、その各桁の合計が3で割り切れることです。そこで、数字を3で割った余り(0・1・2)ごとにグループ分けし、合計が3の倍数になるよう最小限の数字を取り除く方針で解きます。

手順

• 3行からなる2次元配列 d を定義する
• 配列 digits を降順にソートする
• sum := 0 で初期化する
• i := 0 から digits のサイズ未満の間、以下を繰り返す
  • x := digits[i]
  • d[x mod 3] の末尾に digits[i] を追加する
  • sum := sum + x
  • sum := sum mod 3
• sum が 0 でない場合、以下を行う
  • d[sum] のサイズが 0 の場合
    • rem := 3 - sum とする
    • d[rem] のサイズが 2 未満なら空文字列を返す
    • d[rem] の末尾から要素を2つ削除する
  • それ以外の場合
    • d[sum] の末尾から要素を1つ削除する
• ret := 空文字列 で初期化する
• i := 0 から 3 未満の間、以下を繰り返す
  • j := 0 から d[i] のサイズ未満の間、ret に d[i][j] を文字列として連結する
• ret を降順にソートする
• ret のサイズが 0 でなく、ret[0] が '0' と等しい場合は "0" を返す
• ret を返す

アルゴリズムのポイント

合計が3で割り切れない場合、取り除くべき数字の候補は次の2パターンだけです。余りの合計が 1 のときは「余り1の数字を1個」または「余り2の数字を2個」を、余りの合計が 2 のときは「余り2の数字を1個」または「余り1の数字を2個」を取り除けばよいことになります。降順ソートしておけば配列の末尾には最も小さい数字が集まるため、末尾から削除することで結果の数値を最大に保てます。また、結果が "00" のようになるケースに備えて "0" への正規化も行っています。

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