C++로 2, 3, 5의 가장 큰 배수 찾기

이 문제에서는 한 자리 숫자(0~9)로만 구성된 크기 N의 배열 arr[]가 주어집니다. 우리의 목표는 2, 3, 5 모두로 나누어 떨어지는 가장 큰 수를 찾는 것입니다.

문제 이해를 위한 예시

입력 : arr[] = {1, 0, 5, 2}
출력 : 510

설명 −

숫자 510은 2, 3, 5 모두로 나누어 떨어집니다.
(510 ÷ 2 = 255, 510 ÷ 3 = 170, 510 ÷ 5 = 102)

해결 접근 방법

이 문제의 간단한 해결 방법은 조합된 숫자가 기본적인 나눗셈 조건을 만족하는지 확인하는 것입니다.

먼저, 어떤 수가 2와 5로 동시에 나누어 떨어지려면 10의 배수여야 합니다. 따라서 10의 배수를 만들려면 배열에 반드시 0이 포함되어 있어야 합니다.

배열에 0이 존재한다면, 다음 단계는 끝자리가 0이면서 3으로 나누어 떨어지는 가장 큰 수를 만드는 것입니다. 이는 "C++에서 3의 가장 큰 배수 찾기" 문제와 동일한 로직을 활용하면 됩니다.

3의 배수 판정법에 따르면, 각 자릿수의 합이 3으로 나누어 떨어지면 그 수도 3으로 나누어 떨어집니다. 따라서 전체 자릿수 합을 3으로 나눈 나머지를 계산하고, 나머지가 남는 경우 해당 나머지를 상쇄할 수 있는 최소한의 자릿수를 제거하여 조건을 만족시킵니다.

예제 코드

아래 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string largestMultipleOfThree(vector<int>& digits) { 
        vector<vector<int>> d(3);
        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;
    }
};
int main(){ 
   Solution ob;
   vector<int> v = {7, 2, 0, 8};
   sort(v.begin(), v.end(), greater<int>()); 
   if(v[v.size() - 1 ] != 0){
      cout<<"만들 수 없습니다!";
   }
   else{
      cout<<"가장 큰 수는 "<<(ob.largestMultipleOfThree(v));
   }
}

실행 결과

가장 큰 수는 870

코드 설명

위 코드의 핵심 로직은 다음과 같습니다.

1. 자릿수 분류 : 각 숫자를 3으로 나눈 나머지(0, 1, 2)에 따라 세 개의 그룹으로 분류하고, 전체 합을 3으로 나눈 나머지를 추적합니다.

2. 나머지 처리 : 합이 3으로 나누어 떨어지지 않는 경우, 나머지와 같은 그룹에서 숫자 하나를 제거하거나, 해당 그룹이 비어 있으면 보완 그룹(rem = 3 - sum)에서 두 개의 숫자를 제거합니다.

3. 결과 생성 : 남은 숫자들을 내림차순으로 정렬하여 가장 큰 수를 만듭니다. 만약 결과가 0으로만 구성되어 있다면 "0"을 반환합니다.

또한 main 함수에서는 배열에 0이 없는 경우 10의 배수를 만들 수 없으므로 "만들 수 없습니다!"를 출력하도록 처리했습니다.