Quiz) 3의 배수인지 확인해보자

Problem

Given a string str representing a number having N digits, the task is to calculate the number of ways to make the given number divisible by 3 by changing at most one digit of the number.

특정 정수 N이 주어집니다. 그리고 우리는 이 정수 N에서 하나의 자릿수의 숫자를 변경할 수 있습니다. 이때 변경할 수 있는 숫자 중, 3으로 나누어질 수 있는 숫자는 몇 개인지 확인해보는 문제입니다.

 

Example

예시는 다음과 같습니다.

Input: str[] = “23”
Output: 7
Explanation: Below are the numbers that can be made from the string which are divisible by 3 – 03, 21, 24, 27, 33, 63, 93
1.Change 2 to 0 (0+3)=3 divisible by 3
2.Change 3 to 1 (2+1)=3 divisible by 3
3 change 3 to 4 (2+4)=6 divisible by 3
4 change 2 to 3 sum is 6 divisible by 3
Similarly there are total 7 number of ways to make the given number divisible by 3

Input: str[] = “235”
Output: 9

 

Approach

위의 예시에서 3으로 나눌 수 있는 숫자를 찾는 과정으로 모든 자릿수의 합을 찾는 내용이 있습니다. 이를 `배수판정법`이라고 하는데요. 3의 배수를 찾는 원리는 다음과 같습니다.

 

abcde라는 임의의 5 자릿수 정수가 있다고 가정해봅니다.

abcde = a(1+9999) + b(1+999) + c(1+99) + d(1+9) + e(1)

여기서 무언가 보이시죠?  위 풀이를 보면 각 자릿수는 9999처럼 3의 배수와 1로 나눌 수 있습니다. 이를 좀 더 풀어보면 다음과 같습니다.

abcde = (9999a+999b+99c+9d) + (a+b+c+d+e)
      = 3(3333a+333b+33c+3d) + (a+b+c+d+e)

이처럼 좌측에는 3의 배수로 나눌 수 있기 때문에 우측 (a+b+c+d+e) 즉, 각 자릿수의 정수합이 3의 배수가 되면 그 수는 3으로 나눌 수 있게 됩니다.

 

주어진 문제 예시를 보면 다음과 같습니다.

# 3의 배수가 아닌 경우
23 = 2(1+9) + 3(1)
   = 2*9 + (2+3)
   = 2*3*3 + 5
   
# 3의 배수인 경우
21 = 2(1+9) + 1(1)
   = 2*9 + (2+1)
   = 2*3*3 + 3

이제 문제에 대한 접근 방법을 알았으니 코드로 넘어가 보도록 하겠습니다.

 

Solution (Java)

package algorithm;

import java.util.HashSet;
import java.util.Set;

/**
 * @Reference: https://box0830.tistory.com/380
 */
public class DivisibilityRule {

    public static void main(String[] args) {
        String[] inputs = {"23", "235"};
        DivisibilityRule divisibilityRule = new DivisibilityRule();

        for (String input : inputs) {
            int count = divisibilityRule.countDivisibleByThree(input);
            System.out.printf("Input `%s` can be replaced with `%d` digits %n", input, count);
        }
    }

    protected int countDivisibleByThree(String input) {
        int sum = 0;
        Set<String> sums = new HashSet<>();

        for (int i = 0; i < input.length(); i++) {
            sum += input.charAt(i);
        }

        int count = 0;
        if (sum % 3 == 0) {
            sums.add(input);
            count++;
        }

        for (int i = 0; i < input.length(); i++) {
            int reSum = sum - input.charAt(i);

            for (int j = 0; j <= 9; j++) {
                StringBuilder temp = new StringBuilder(input);
                temp.setCharAt(i, (char) (j + '0'));
                if ((reSum + j) % 3 == 0 && j != input.charAt(i) && !sums.contains(temp.toString())) {
                    count++;
                    sums.add(temp.toString());
                }
            }
        }

        return count;
    }

}

주의할 점은 자릿수를 바꾸는 도중에 중복되는 값이 도출될 수 있다는 점입니다. 이를 대비해서 한번 3의 배수로 체크한 값은 `Set`을 이용하여 중복 확인을 하도록 하였습니다.

 

Review 

`배수판정법`은 제 학창 시절부터 지금까지 가장 자주 나오는 수학 알고리즘 문제 중 하나입니다. 그만큼 다양한 문제가 출제되고 있으며 3의 배수뿐만 아니라 9의 배수, 심지어 5의 배수 등을 물어보는 문제도 종종 보이곤 합니다. 알고리즘 시험을 준비하는 분이라면 한 번씩은 확인하고 넘어가면 좋을 것 같습니다.

 

위키백과의 배수 판정법 링크를 달며 이번 포스팅은 마무리하도록 하겠습니다.

배수 판정법 - 위키백과, 우리 모두의 백과사전

 

Reference

https://www.geeksforgeeks.org/count-of-different-numbers-divisible-by-3-that-can-be-obtained-by-changing-at-most-one-digit/

Count of different numbers divisible by 3 that can be obtained by changing at most one digit - GeeksforGeeks