[Javascript] Codility Lesson 5 - CountDiv

 

문제: https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/start/

 

문제 요약: 

• 정수 A와 정수 B 사이에서 K로 나뉘어 떨어지는 수의 개수 구하기 (A <=... <=B)
• A와 B는 0 이상 2000000000 이하의 숫자
• K는 1 이상 2000000000 이하의 숫자
• A <= B

function solution(A, B, K) {
    let result = 0;
    let target = A;

    while (target <= B) {
        if (target % K === 0) {
            result += 1;
            target += K;
        } else {
            target += 1;
        };
    };

    return result;
}

https://app.codility.com/

A 이상 B 이하의 모든 숫자를 하나씩 순환하는 것을 피하기 위해, 두 숫자 사이에 K의 배수를 찾아 카운팅 했다. 하지만 퍼포먼스 효율성이 현저히 떨어지는 결과가 나왔다. 어찌 보면 당연한 결과인 게, A가 2, B가 2000000000, K가 2라고 가정했을 때 결국 1000000000번을 순환해야 결과 값을 얻을 수 있다. 그래서 단순히 생각하여 다시 코드를 작성했다.

 

 

개선 시도 1: (B / K의 몫) - (A / K의 몫)

function solution(A, B, K) {
    let a = Math.floor(A / K);
    let b = Math.floor(B / K);

    return A % K === 0 ? b - a + 1 : b - a;
}

https://app.codility.com/

B 이하의 숫자 중 K의 배수가 되는 모든 숫자의 개수(Math.floor(B / K))를 구하고,  A 이하의 숫자 중 K의 배수가 되는 모든 숫자의 개수(Math.floor(A / K))를 구한 뒤, 전자에서 후자를 빼면 A와 B 사이에 있는 K의 배수 개수를 얻을 수 있다. 다만 무작정 빼면 "A <=... <= B" 조건에 어긋날 수 있다. 그래서 A / K를 했을 때 나누어 떨어질 경우 A도 포함하기 위해 b - a + 1, 나머지가 나오면 b - a의 결과를 반환하도록 했다.

시간 복잡도:  O(1)