24.1) 문제 이해
꼬리에 붙은 0의 문제 및 목표
- 주어진 숫자의 팩토리얼을 계산한 값에서, 마지막에 연속되어 붙어있는 0이 몇 개인지 반환해주는 함수를 완성해야 합니다.
꼬리에 붙은 0의 조건
- 팩토리얼을 꼭 계산할 필요는 없습니다.
- 참고로 n 팩토리얼이란 다음과 같습니다.
- n! = 1 * 2 * 3 * 4 * … * n
- 예를 들어, trailingZeros(6) = 1 입니다.
- 왜냐하면 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720이고 끝에 1개의 0이 있습니다.
24.2) 해결 방법
- ① n이 큰 숫자라면 n!은 컴퓨터로는 계산할 수 없습니다. 왜냐하면 계산할 수 있는 범위를 초과하기 때문입니다. 따라서 팩토리얼을 계산하지 않고 0이 몇 개인지 셀 수 있어야 합니다.
- ② 1!부터 10!까지 쭉 써보면, 아래와 같습니다.
- ③ 팩토리얼을 자세히 보면 끝자리에 0이 붙는 갯수는 10의 갯수에 따라 달라집니다. 5!을 보면 2 * 5 = 10이고 1개만 있으므로 최종 계산값인 120에 0이 하나만 있습니다. 그리고 10!을 보면 2 * 5와 10 두 개가 있으므로 0이 두 개가 붙어있습니다.
- ④ 10!을 풀어헤쳐 써보면 10! = 1 * 2 * 3 * 2 * 2 * 5 * 2 * 3 * 7 * 2 * 2 * 2 * 3 * 3 * 2 * 5라고 쓸 수 있습니다. 이 때 10을 만드는 2의 갯수와 5의 갯수는 각각 8개, 2개입니다. 따라서 2의 갯수는 충분하므로 5의 갯수가 0의 갯수를 결정한다는 것을 알 수 있습니다.
- ⑤ 그러므로 5의 배수가 몇 개인지를 찾으면 문제를 해결할 수 있습니다. 그런데 여기서 25와 125 등 5의 배수 중에는 5*5와 5*5*5로 이루어진 숫자도 있습니다. 이 숫자들은 0을 각각 2개, 3개씩 만들게됩니다.
24.3) 코드 구현
- 0의 갯수를 셀 변수 count를 선언하고 0으로 초기화합니다.
- 입력된 n에 5의 배수가 몇 개있는지 확인하기 위해 for문을 사용합니다.
- for문을 사용하는 이유는 5는 0을 하나 만들어내는 반면에 25와 125와 같이 5의 배수 중에 0을 2개, 3개씩 만들어내는 숫자도 있으므로 그러한 숫자가 추가로 0을 몇 개 더 만들어냈는지 세기 위해 5의 배수가 n보다 커지기 전까지 반복해서 나눠봅니다.
- n = 100이라고 했을 때, 처음에 5로 나누면 20이 나오고 20은 5가 만들어낸 0의 갯수입니다.
- 그리고 아직 5의 배수가 n보다 작기 때문에 다시 for문이 돕니다.
- 이번엔 25로 100을 나누게 되고 4가 나옵니다. 4는 25로 인해 만들어진 0의 갯수입니다.
- 다시 for문을 돌리기 전 조건식을 확인하지만 125는 n = 100 보다 크기 때문에 그대로 종료됩니다.
- 그리고 count = 20 + 4 =24 이고 24가 최종 0의 갯수입니다.
24.4) 결과 분석
- 주어진 Test 환경에서 모두 Pass 하였습니다.
