Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

숫자 배열에서 3의 가장 큰 배수 찾기 - C++에서 2로 설정


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

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

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

  • 하나의 2D 배열 d를 정의하면 3개의 행이 있습니다.

  • 배열 숫자 정렬

  • 합계 :=0

  • 초기화 i :=0의 경우, i <자릿수 크기일 때 업데이트(i를 1만큼 증가), 수행 -

    • 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"을 반환

  • 리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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