문제 소개
크기가 N인 양의 정수 배열 Arr[]가 주어졌을 때, 배열의 모든 원소를 곱한 결과에서 뒤에 붙는 0(trailing zero)의 개수를 구하는 것이 목표입니다.
이 문제는 각 숫자의 인수를 세는 방식으로 해결할 수 있습니다. 2와 5의 곱이 10이 되어 후행 0을 하나 만들어 내기 때문에, 각 원소에서 2와 5가 각각 몇 번씩 등장하는지 세면 됩니다. 최종적으로는 두 카운트 중 더 작은 값이 곱의 후행 0 개수가 됩니다.
예를 들어 2가 4개, 5가 6개 있다면 곱에는 4개의 후행 0이 생깁니다.
2 × 2 × 2 × 2 × 5 × 5 × 5 × 5 × 5 × 5 = 250000
예제 1
입력
Arr[] = { 2, 5, 10, 15, 20, 25, 100 }출력
후행 0의 개수 : 6
설명
배열의 각 원소에서 2와 5의 누적 개수:
Arr[0] = 2 : 2 → twos=1, fives=0
Arr[1] = 5 : 5 → twos=1, fives=1
Arr[2] = 10 : 2×5 → twos=2, fives=2
Arr[3] = 15 : 3×5 → twos=2, fives=3
Arr[4] = 20 : 2×2×5 → twos=4, fives=4
Arr[5] = 25 : 5×5 → twos=4, fives=6
Arr[6] = 100 : 2×2×5×5 → twos=6, fives=8
2의 개수(6)가 5의 개수(8)보다 적으므로 후행 0은 6개입니다.
예제 2
입력
Arr[] = { 10, 10, 10, 10, 10 }출력
후행 0의 개수 : 5
설명
배열의 각 원소에서 2와 5의 누적 개수:
Arr[0] = 10 : 2×5 → twos=1, fives=1
Arr[1] = 10 : 2×5 → twos=2, fives=2
Arr[2] = 10 : 2×5 → twos=3, fives=3
Arr[3] = 10 : 2×5 → twos=4, fives=4
Arr[4] = 10 : 2×5 → twos=5, fives=5
2와 5의 개수가 같으므로 후행 0은 5개입니다.
알고리즘 접근 방식
길이가 N인 양의 정수 배열을 입력받습니다.
trailZeros(int arr[], int n) 함수는 배열과 크기 n을 입력으로 받아, 모든 원소의 곱에 포함된 후행 0의 개수를 반환합니다.
후행 0의 개수를 저장할 변수 count를 0으로 초기화합니다.
인수로 등장하는 2와 5의 개수를 세기 위한 변수 twos와 fives를 준비합니다.
for 반복문으로 배열을 순회합니다.
각 원소가 2 또는 5로 나누어 떨어지는 동안 해당 값으로 나누고, twos 또는 fives를 1씩 증가시킵니다.
반복문이 끝나면 twos와 fives 값을 비교하여 더 작은 쪽을 선택합니다.
두 값 중 작은 값으로 count를 초기화한 뒤 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int trailZeros(int arr[], int n){
int count = 0;
int twos = 0;
int fives = 0;
for (int i = 0; i < n; i++){
while(arr[i]%2==0 || arr[i]%5==0){
if(arr[i]%2==0){
arr[i]=arr[i]/2;
twos++;
}
if(arr[i]%5==0){
arr[i]=arr[i]/5;
fives++;
}
}
}
count = twos<fives ? twos : fives;
return count;
}
int main(){
int Arr[]={ 12, 5, 15, 8, 100, 40 };
int Length = sizeof(Arr)/sizeof(Arr[0]);
cout << endl << "후행 0의 개수 : " << trailZeros(Arr, Length);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
후행 0의 개수 : 5
배열 { 12, 5, 15, 8, 100, 40 }의 경우, 전체 곱에서 2는 10개, 5는 5개 등장하므로 더 작은 값인 5가 후행 0의 개수가 됩니다.