Codility Lesson11 - CountNonDivisible

🔍 문제

---

 

어떤 주어진 배열 A의 원소인 A[i]의 약수가 아닌 원소가 해당 배열에 몇개인지 구하는 문제이다.

 

CountNonDivisible coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

 

원소 A[i]의 약수가 아닌 수는 전체 원소의 개수에서 약수인 수를 빼서 구했다.

맨 처음에는 배열안에서 각각의 수가 몇개인지 구해준다. 원소의 개수를 담는 배열의 범위는 idx값이 1부터 N*2까지 담을 수 있도록 만들었다. 왜냐하면 문제의 조건 중에 A[I]의 원소가 될 수 있는 범위는 1부터 N*2까지 이기 때문이다. 처음에 이 조건을 제대로 안보고 풀려고 하다보니 조금 헤맸다.

 

그리고나서 배열 A를 순회하면서 약수 j = 1부터 시작해서 A의 원소를 나누기 시작한다. 만약에 나눠지면, numCnt배열에서 해당 약수의 개수를 divisors개수에 합해주었다. 그리고나서 A[i]/j의 값이 j가 아니라면 이 수 역시 약수가 되기 때문에 numCnt에서 찾아서 divisors에 더해준 후 전체 배열의 개수인 N에서 빼주었다.

 

시간 복잡도는 O(N * log(N))가 나왔으며 total 100%가 나왔다.

 

이전 문제도 그렇고 배열을 채처럼 이용해서 푸는 방식이 생소하기도해서 로직을 코드로 구현하는데 어려움을 겪었다. 두고두고 보면서 익숙해질 필요가 있을 것 같다.

function solution(A) {

    const N = A.length;

    //배열 A의 원소가 몇개인지 담을 배열 생성
    let numCnt = new Array((N * 2)+1).fill(0);

    for(let i in A) {
        numCnt[A[i]]++;
    }


    //각 원소의 약수 개수 세기    
    let divCnt= [];

    for(let i = 0; i < N; i++) {
        let divisors = 0;

        for(let j = 1; j * j <= A[i]; j++) {
            if(A[i] % j === 0) {
                divisors += numCnt[j];

                if(A[i] / j !== j) {
                    divisors += numCnt[A[i]/j];
                }
            }
        }

        divCnt[i] = N - divisors; //배열 A의 원소 개수에서 약수의 개수를 빼준다.
    }

    return divCnt;

}