파이썬으로 n개의 숫자를 곱한 후 끝에 연속되는 0의 개수 구하기

문제 개요

n개의 숫자로 이루어진 배열이 주어졌을 때, 배열의 모든 숫자를 곱한 결과값 끝에 연속해서 붙어 있는 0의 개수를 구하는 문제입니다.

예를 들어 입력이 [200, 20, 5, 30, 40, 14]라면, 200 × 20 × 5 × 30 × 40 × 14 = 336000000이 되고, 마지막에 0이 여섯 개 연속으로 이어져 있으므로 정답은 6입니다.

핵심 아이디어: 2와 5의 짝

곱셈 결과 끝에 붙는 0은 소인수분해했을 때 2와 5가 한 쌍을 이룰 때마다 하나씩 생깁니다. 10 = 2 × 5이기 때문입니다. 따라서 전체 곱에서 2의 총 개수와 5의 총 개수를 각각 센 뒤, 그중 더 작은 값이 곧 연속된 0의 개수가 됩니다.

이 방식의 가장 큰 장점은 실제로 매우 큰 곱셈 결과를 직접 계산할 필요가 없다는 점입니다. 숫자가 아무리 커져도 오버플로우 걱정 없이 빠르게 답을 구할 수 있습니다.

풀이 알고리즘

다음 단계에 따라 문제를 해결합니다.

count_fact_two() 함수를 정의합니다. 인자로 받은 n이 2로 나누어떨어지지 않을 때까지 계속 2로 나누면서 나눈 횟수를 반환합니다.
count_fact_five() 함수를 정의합니다. 같은 방식으로 n이 5로 나누어떨어지지 않을 때까지 나누면서 나눈 횟수를 반환합니다.
메인 로직에서 다음을 수행합니다.
- 배열 A의 크기를 n에 저장하고, twos와 fives를 0으로 초기화합니다.
- 배열의 각 원소에 대해 count_fact_two()와 count_fact_five()의 결과를 각각 누적합니다.
- twos와 fives 중 더 작은 값을 반환합니다.

파이썬 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

def count_fact_two(n):
    count = 0
    while n % 2 == 0:
        count += 1
        n = n // 2
    return count

def count_fact_five(n):
    count = 0
    while n % 5 == 0:
        count += 1
        n = n // 5
    return count

def get_consecutive_zeros(A):
    n = len(A)
    twos = 0
    fives = 0
    for i in range(n):
        twos += count_fact_two(A[i])
        fives += count_fact_five(A[i])
    if twos < fives:
        return twos
    else:
        return fives

A = [200, 20, 5, 30, 40, 14]
print(get_consecutive_zeros(A))

실행 결과

입력:

[200, 20, 5, 30, 40, 14]

출력:

시간 복잡도

각 숫자에 대한 나눗셈 반복 횟수는 해당 수의 크기에 따라 최대 log(숫자) 수준이므로, 전체 시간 복잡도는 O(n log m)입니다(m은 배열 내 최댓값). 공간 복잡도는 O(1)로, 추가 메모리 사용 없이 효율적으로 해결할 수 있습니다.