문제

n이라는 숫자가 주어졌을 때, n 팩토리얼의 결과값에서 뒤쪽에 위치한 연속된 0의 개수를 반환하세요.

제한 사항

• 0 <= n <= 10^4

입출력 예

n	result
3	0
5	1
0	0

정답

const factorial = (n) => {
    let num = BigInt(1);

    while (n > 1) {
        num = num * BigInt(n);
        n -= 1;
    }

    return num;
}

const trailingZeroes = (n) => {
    const num = factorial(n);

    if (num > 9) {
        const zeros = String(num).match(/0*0$/);
        return zeros ? zeros[0].length : 0;
    }

    return 0;
};

풀이

factorial이라는 재귀함수를 통해 n!의 값을 구하고 이후 문자열로 변환한 뒤 정규표현식을 통해 뒤쪽에 위치한 연속된 개수의 0을 세어 반환하도록 코드를 작성하였습니다.

제한사항을 보면 n이 최대 10^4까지 될 수 있기 때문에 Number타입이 표현할 수 있는 숫자를 넘어설 수 있어
이를 위해 연산시 BigInt타입으로 변환해 연산이 이루어질 수 있도록 처리했습니다.

리팩토링

위에서 작성한 코드를 제출한 후 3779ms라는 실행 속도를 확인했고 다른 사람들의 답안에 비해 성능이 확연히 떨어지는것을 확인하였습니다.

또한, 문제 지문의 하단에서 시간복잡도 O(log n)으로 풀어보면 좋다고 하여 팩토리얼 값에 규칙성이 있을 거 같아 1! ~ 200!까지의 출력값들을 확인해보았습니다.

사진에서 zeros는 팩토리얼값의 뒤쪽의 연속된 0의 개수를 나타내는데 사진에서 보이듯이 일정한 규칙성을 갖고 있는것을 확인했습니다.

5단위로 0의 개수가 1씩 올라가는데 특이한 점이 25, 50, 75, 100에서는 1이 추가적으로 더 올라가 해당 숫자에서는 2씩 상승되는걸 확인할 수 있습니다.

즉, 팩토리얼값의 뒤쪽에 위치한 연속된 0의 개수는 i의 값을 5로 나눴을 때의 몫의 개수가 되며 해당 몫이 5로 나눠질 수 있다면 그만큼 0이 더 늘어난다는 규칙성을 확인할 수 있었습니다.

그래서, 위와 같은 규칙성을 바탕으로 아래 코드로 리팩토링을 진행하였고 58ms라는 만족스러운 성능을 확인할 수 있었습니다.

const trailingZeroes = function(n, zeros = 0) {
    if (n < 5) return zeros;

    const quotient = Math.floor(n / 5);
    zeros += quotient;

    return trailingZeroes(quotient, zeros);
};