C++에서 숫자를 3의 배수로 만들기 위해 제거해야 할 자릿수 구하기

문제 개요

문자열 형태로 주어진 숫자를 3으로 나누어 떨어지게 만들려면 몇 개의 자릿수를 제거해야 하는지 구하는 문제입니다.

흥미롭게도 어떤 숫자든 최대 2개의 자릿수만 제거하면 3의 배수로 만들 수 있습니다. 따라서 이 문제에서 제거해야 할 자릿수의 최댓값은 2입니다.

예제 1

입력

출력

자릿수 2를 제거하면 9가 남고, 9는 3으로 나누어 떨어집니다.

예제 2

입력

출력

주어진 숫자 자체가 이미 3의 배수이므로 아무것도 제거할 필요가 없습니다.

핵심 원리

어떤 수가 3으로 나누어 떨어지려면 각 자릿수의 합이 3의 배수여야 합니다. 이 성질을 이용하면 전체 자릿수의 합에서 특정 자릿수를 뺀 값이 3으로 나누어 떨어지는지만 확인하면 됩니다. 즉, (전체 합 mod 3)과 (해당 자릿수 mod 3)가 같다면 그 자릿수 하나만 제거하면 됩니다.

한 자릿수 제거로 해결되지 않는 경우에도, 자릿수가 3개 이상이라면 두 자릿수를 제거하는 방법이 반드시 존재합니다.

알고리즘

숫자를 문자열로 초기화합니다.
각 자릿수의 합을 구합니다.
합이 3으로 나누어 떨어지면 0을 반환합니다.
합이 3으로 나누어 떨어지지 않는데 숫자의 길이가 1이라면 3의 배수로 만들 수 없으므로 -1을 반환합니다.
숫자를 순회하면서 자릿수를 하나씩 검사합니다.
- 해당 자릿수를 제거했을 때 나머지 숫자가 3으로 나누어 떨어지는지 확인합니다.
- 조건을 만족하면 1을 반환합니다.
숫자의 길이를 다시 확인합니다. 길이가 2라면 -1을 반환합니다.
그 외의 경우 2를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

// 각 자릿수의 합을 구하는 함수
int getNumSum(string n) {
    int len = n.length(), sum = 0;
    for (int i = 0; i < len; i++) {
        sum += n[i] - '0';
    }
    return sum;
}

// 제거해야 할 자릿수의 개수를 구하는 함수
int getDigitsCount(string num) {
    int n = num.length();
    int sum = getNumSum(num);

    // 이미 3의 배수인 경우
    if (sum % 3 == 0) {
        return 0;
    }

    // 한 자릿수는 더 이상 줄일 수 없음
    if (n == 1) {
        return -1;
    }

    // 자릿수 하나를 제거해서 해결되는지 확인
    for (int i = 0; i < n; i++) {
        int currentDigit = num[i] - '0';
        if (sum % 3 == currentDigit % 3) {
            return 1;
        }
    }

    // 두 자릿수로는 해결 불가
    if (n == 2) {
        return -1;
    }

    // 세 자릿수 이상이면 두 번의 제거로 항상 가능
    return 2;
}

int main() {
    string num = "7536836";
    cout << getDigitsCount(num) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

예제 숫자 7536836의 자릿수 합은 38이고, 38을 3으로 나눈 나머지는 2입니다. 자릿수 8(8 mod 3 = 2)을 제거하면 753636이 되며, 이때 자릿수의 합이 30으로 3의 배수가 되므로 정답은 1입니다.