C++에서 가장 큰 3의 배수

<시간/>

하나의 숫자 배열이 있다고 가정하고 원하는 순서대로 주어진 숫자 중 일부를 연결하여 형성할 수 있는 3의 가장 큰 배수를 찾아야 합니다. 답변이 매우 클 수 있으므로 문자열로 만드십시오. 응답이 없으면 빈 문자열을 반환합니다.

따라서 입력이 [7,2,8]과 같으면 출력은 87

이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 2D 배열 d를 정의하면 3개의 행이 있습니다.
배열 숫자 정렬
합계 :=0
for initialize i :=0, i <자릿수, 업데이트(i 1 증가), do−
- x :=숫자[i]
- d[x mod 3]
  끝에 숫자[i] 삽입
- 합계 :=합계 + x
- 합계 :=합계 모드 3
합계가 0이 아니면 -
- d[sum]의 크기가 아니면 -
  - rem :=3 - 합계
  - 크기가 d[rem] <2이면 -
    - 빈 문자열 반환
  - d[rem]에서 마지막 요소를 두 번 삭제
- 그렇지 않으면
  - d[sum]
    에서 마지막 요소 삭제
ret :=빈 문자열
initialize i :=0의 경우, i <3일 때 업데이트(i를 1만큼 증가), 수행 -
- j 초기화의 경우:=0, j
  - ret :=ret d[i, j]를 문자열로 연결
ret 배열 정렬
ret 및 ret[0]의 크기가 '0'과 같으면 -
- "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 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}