Python으로 배열의 모든 숫자를 사용해 3의 배수를 만들 수 있는지 확인하는 방법

이 글에서는 주어진 문제를 해결하기 위한 접근 방식과 풀이 과정을 살펴보겠습니다.

문제 정의

정수로 이루어진 배열이 주어졌을 때, 배열에 포함된 모든 숫자(자릿수)를 사용하여 만들 수 있는 수가 3으로 나누어 떨어지는지 판별해야 합니다.

여기서는 정수 배열과 배열의 길이, 두 가지 인자를 받는 함수를 작성하겠습니다.

핵심 아이디어

이 문제는 암산에 활용되는 수학적 성질을 이용하면 간단히 해결할 수 있습니다. 바로 어떤 수의 각 자릿수 합이 3으로 나누어 떨어지면, 그 수 역시 3으로 나누어 떨어진다는 성질입니다.

따라서 배열의 모든 요소를 더한 값이 3으로 나누어 떨어지는지만 확인하면 됩니다. 각 숫자를 하나씩 더하면서 3으로 나눈 나머지를 누적 계산하면 효율적으로 처리할 수 있습니다.

구현 예제

def isPossibleToMakeDivisible(arr, n):
    remainder = 0
    for i in range(0, n):
        remainder = (remainder + arr[i]) % 3
    return (remainder == 0)

# main()
arr = [33, 40, 90]
n = 3
if (isPossibleToMakeDivisible(arr, n)):
    print("Yes")
else:
    print("No")

실행 결과

No

코드 설명

위 코드의 동작 과정은 다음과 같습니다.

1. remainder 변수를 0으로 초기화합니다.
2. 반복문을 통해 배열의 각 요소를 차례대로 더하고, 매번 3으로 나눈 나머지를 저장합니다.
3. 모든 요소를 처리한 후 나머지가 0이면 True, 그렇지 않으면 False를 반환합니다.

예제 배열 [33, 40, 90]의 경우, 각 자릿수의 합은 3+3+4+0+9+0 = 19이고, 19를 3으로 나누면 나머지가 1이므로 결과는 "No"가 출력됩니다.

시간 복잡도는 O(n)으로, 배열의 크기에 비례하여 선형 시간 안에 문제를 해결할 수 있습니다.

결론

이 글에서는 배열에 포함된 모든 숫자를 사용하여 3으로 나누어 떨어지는 수를 만들 수 있는지 확인하는 방법을 알아보았습니다. 자릿수 합의 성질을 활용하면 실제로 수를 조합해 보지 않고도 O(n) 시간 복잡도로 간단하게 판별할 수 있다는 점이 핵심입니다.