Codility Lesson10 - CountFactors

🔍 문제

---

 

CountFactors coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

첫 번째 풀이는 어렸을 때 수학 시간에 배운 어떤 수의 약수 개수 구하기가 생각나서 그 방식으로 풀어 보았다.
N을 소인수 분해한 후, 각 소인수의 지수+1을 해준 후 곱한 수를 반환하였다. 정확도는 100%가 나왔지만 문제는 performance에서 timeout error가 발생하였다. 만약 매우 큰 소수가 N(ex. 780291637)으로 들어올 경우 while문에서 i++를 해가면서 i가 N이 될 때까지 매우 오랜 시간이 걸렸다. 또, 정수 타입 중 가장 큰 값이 N으로 들어오면 시간 초과가 발생하였다. 따라서 다른 방법으로 풀어보기로 했다.

function solution(N) {
    let map = new Map();
    let i = 2;

    while(true) {
        if(N === 1) break;
        if(N % i === 0) {
            if(!map.has(i)) map.set(i, 0);
            map.set(i, map.get(i)+1);
            N = N / i;
        } else {
            i++;
        }
    }

    let factorCnt = 1;

    for(let value of map.values()) {
        factorCnt *= value+1;
    }

    return factorCnt
}

따라서 두번째 풀이는 아래와 같이 풀어보았다. 예를 들어, N = 100이라면, 1, 2, 4, 5, 10(=Math.sqrt(100)), 20, 25, 50, 100이 약수이다.
만약 Math.sqrt(N)이 정수라면, Math.sqrt(N)가 N의 약수가 되며, 나머지 약수들은 Math.sqrt(N)을 기준으로 앞 뒤로 짝을 이루고 있다.
따라서 Math.sqrt(N)(= N의 제곱근)을 기준으로 약수의 개수를 구한 후, 그 개수에 *2를 해준다. 그리고 Math.sqrt(N)이 정수라면 Math.sqrt(N)자체가 N의 약수가 되기 때문에 +1을 해주었다. 시간 복잡도는 O(sqrt(N))가 나왔고 이번에는 정확도, performance 모두 통과하였다.

function solution(N) {
    if (N === 1) return 1;

    let factorCnt = 1;

    for(let i = 2; i < Math.sqrt(N); i++) {
        if(N % i === 0) {
            factorCnt++;
        }
    }

    factorCnt = factorCnt * 2;

    if(Math.sqrt(N) % 1 === 0) factorCnt++;

    return factorCnt;
}