[ 구름 ] 시간복잡도 - JavaScript

문제

구름 EDU의 강사인 구름이는 시간복잡도에 대한 강의를 맡게 되었다. 시간복잡도에는 여러 가지가 있는데, 한 번의 산술 연산에 걸리는 상수 시간인 O(1), 이분 탐색에 걸리는 로그 시간인 O(log N), 정렬되지 않은 배열에서 특정한 수를 찾을 때 걸리는 선형 시간인 O(N), 병합 정렬에 걸리는 선형 로그 시간인 O(N log N), 버블 정렬에 걸리는 2차 시간인 O(N²), N개의 비트에서 나올 수 있는 경우를 모두 구할 때 걸리는 지수 시간인 O(2^N)등이 있다. 그리고 주어진 배열의 모든 순열을 구하는 계승 시간인 O(N!)도 있다.

O(N!)은 N이 20만 되어도 243경 정도가 될 정도로 정말 빨리 커진다. 그래서 구름이는 O(N!)이 얼마나 빨리 커지는지 수강생들에게 알려주기 위해, 임의의 N에 따라 N!의 맨 뒤에 붙는 연속된 0의 개수를 구하는 프로그램을 작성하려고 한다.

N이 주어질 때, N!의 맨 뒤에 붙는 연속된 0의 개수를 알아보자.

 

입력

첫째 줄에 정수 N이 주어진다.

1 ≤ N ≤ 10⁹

 

출력

N!의 맨 뒤에 붙는 연속된 0의 개수를 출력한다.

 

입출력 예시

입력 1

10

 

출력 1

2

 

입력 2

1000000000

 

출력 2

249999998

 

 

---

 

 

풀이

const readline = require("readline");

(async () => {
  let rl = readline.createInterface({ input: process.stdin });
  let n;
  let inputLine;

  for await (const line of rl) {
    inputLine = Number(line);
    rl.close();
  }

  console.log(solution(inputLine));

  process.exit();
})();

function solution(num) {
  let result = 0;

  for (let i = 1; ; i++) {
    if (5 ** i > num) break;
    result += Math.floor(num / 5 ** i);
  }
  
  return result;
}

 

이 문제는 정수론을 사용해 빠르게 풀어내야 하는 문제이다.

 

N이 최대 10억이기 때문에 N!을 직접 계산하여 풀 수는 없다. 그렇다면 규칙을 찾아내야 하는데, 임의의 정수 x 뒤에 0이 붙는 조건은 10이 곱해져야 한다. 10은 2 x 5이고 결국 x 뒤에 붙은 연속된 0의 개수는 x를 소인수 분해했을 때 2의 개수와 5의 개수 중 더 작은 값이 답이 될 것이다.

 

이제 소인수분해를 했을 때 소인수 n의 개수를 구하는 방법을 알아야한다. x를 소인수분해 했을 때의 소인수 n의 개수를 구하는 방법은 다음과 같다.

1. 1부터 x까지 n의 배수의 개수를 구한다. ( x를 n으로 나눈 몫과 동일하다 )
2. 1부터 x까지 n²의 배수의 개수를 구한다. ( x를 n²으로 나눈 몫과 동일하다 )
3. n³, n⁴, ... 의 배수의 개수를 구한다.
4. 나온 개수들을 전부 합하면 x를 소인수분해 했을 때의 소인수 n의 개수가 된다.

위와 같은 방법으로 2와 5의 개수를 각각 구해서 둘 중 작은 값을 찾으면 된다. 하지만 굳이 2와 5의 개수를 둘 다 찾을 필요없이 5의 개수만 찾으면 된다. 2는 2, 4, 6, 8, ... 주기로 등장하지만 5는 5, 10, 15, 20, ... 주기로 등장하기 때문에 항상 2의 개수보다 5의 개수가 반드시 같거나 더 작기 때문이다.