เลขคูณของ 3 ที่มากที่สุดใน C++

คำอธิบายโจทย์

กำหนดอาร์เรย์ของตัวเลข (digits) ให้หาเลขคูณของ 3 ที่มากที่สุดที่สามารถสร้างได้โดยการนำตัวเลขมาเรียงต่อกันในลำดับใดก็ได้ คำตอบอาจใหญ่มาก จึงคืนค่าเป็น string หากไม่มีคำตอบให้คืน string ว่าง

ตัวอย่าง

Input: [7,2,8] → Output: "87" (เพราะ 87 หาร 3 ลงตัว และมากที่สุด)

วิธีแก้ปัญหา

1. จัดกลุ่มตัวเลขตาม modulo 3: d[0], d[1], d[2]
2. เรียงตัวเลขจากมากไปน้อย
3. คำนวณผลรวม modulo 3 (sum)
4. ถ้า sum != 0:
   • ถ้ามีตัวเลขในกลุ่ม d[sum] → ลบตัวเลขน้อยสุดออก 1 ตัว
   • ไม่มี → ลบตัวเลขน้อยสุด 2 ตัวจากกลุ่ม d[3-sum]
5. รวมตัวเลขที่เหลือ เรียงจากมากไปน้อยต่อเป็น string
6. กรณีพิเศษ: ถ้าตัวแรกเป็น '0' → คืน "0"

การทำงานของโค้ด

#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 x : digits) {
            d[x % 3].push_back(x);
            sum = (sum + x) % 3;
        }
        
        if (sum) {
            if (d[sum].empty()) {
                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 x : d[i])
                ret += to_string(x);
        
        sort(ret.begin(), ret.end(), greater<char>());
        if (!ret.empty() && ret[0] == '0') return "0";
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {7,2,8};
    cout << ob.largestMultipleOfThree(v);
    return 0;
}

อินพุต

{7,2,8}

เอาต์พุต

87