(Codility) CountNonDivisible - Javascript

문제

You are given an array A consisting of N integers.

For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.

For example, consider integer N = 5 and array A such that:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6

For the following elements:

• A[0] = 3, the non-divisors are: 2, 6,
• A[1] = 1, the non-divisors are: 3, 2, 3, 6,
• A[2] = 2, the non-divisors are: 3, 3, 6,
• A[3] = 3, the non-divisors are: 2, 6,
• A[4] = 6, there aren't any non-divisors.

Write a function:

function solution(A);

that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6

the function should return [2, 4, 3, 2, 0], as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..50,000];
• each element of array A is an integer within the range [1..2 * N].

 

코드

 

function solution(A) {
    const n = A.length;

    // i 번째 인덱스 === A[i]의 개수
    const countArray = Array((n * 2 + 1)).fill(0);

    for (let i = 0; i < n; i++) {
        countArray[A[i]] += 1;
    }

    let result = [];
    for (let i = 0; i < n; i++) {
        const now = A[i];

        let count = 0;
        for (let j = 1; j ** 2 <= now; j++) {
            if (now % j === 0) {
                count += countArray[j];

                // now / j === j 일 경우 두번 계산되기 때문에 한번 걸러준다.
                if(now / j !== j) {
                    count += countArray[now / j];
                }
                
            }
        }

        result.push(n - count);
    }

    return result;
}

 

 

풀이

 

아래 코드는 맨 처음 풀었던 방식이고

시간복잡도는 O(N**2)로 부분점수만 받았다.

function solution(A) {
    const n = A.length;
    const result = [];
    const cache = {};

    for (let i = 0; i < n; i++) {
        const now = A[i];

        if (cache[now] !== undefined) {
            result.push(cache[now]);
            continue;
        }

        let count = n;
        for (let j = 1; j ** 2 <= now; j++) {
            if (now % j === 0) {
                const quotient = now / j;
                const divisor = j;

                count -= A.filter(d => d === quotient || d === divisor).length;
            }
        }

        if (cache[now] === undefined) {
            cache[now] = count;
            result.push(count);
        }
    }
    
    return result;
}

 

어떻게 줄일까 고민하다가 구글링을 살짝 하였고

 

// i 번째 인덱스 === A[i]의 개수
const countArray = Array((n * 2 + 1)).fill(0);

for (let i = 0; i < n; i++) {
  countArray[A[i]] += 1;
}

 

이런 방식으로 전체 배열에서 각 요소(A[i])의 개수들을 미리 countArray란 배열에 담아둠으로 인해 내가 맨 처음에 구현했던 코드에서 filter 연산을 없앰으로 인해 시간 통과가 된듯 하다!

 

더 분발합시닷! ㅜㅜ