프로그래머스 기사단원의 무기

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/136798?language=javascript

문제 풀이

문제의 핵심은 약수의 갯수를 얼마나 효율적으로 찾는가인다.

일반적으로 1 ~ number까지 for문을 돌면서 나누어 떨어지는 값을 약수로 구할 경우 O(n)의 시간복잡도가 걸린다. -> 시간초과

따라서 효율적으로 약수의 갯수를 찾는 방법은 다음과 같다.

1. 1 ~ number의 제곱근까지 number를 나누었을 때 0이 되는 값이 약수가된다.

2. 해당 값으로 number을 나눈 몫 또한 약수가된다.

3. 중요한 점은 1번에서 구한 값과 2번에서 구한 값의 중복이 발생할 수 있으므로 중복 제거를 해줘야한다. -> set 자료구조 이용

function cal(num) {
    let arr = new Set();
    // 제곱근의 값
    // 1. num의 제곱근 범위로 나머지가 0인 값 구하기
    let tmp = Math.sqrt(num);
    for (let i = 1; i <= tmp; i++) {
        if (num % i === 0) {
            arr.add(i);
            // 2. num을 위에서 구한 약수로 나누었을때 값 구하기
            arr.add(num / i);
        }
    }
    return arr.size;
}

function solution(number, limit, power) {
    let answer = [];
    for (let i = 1; i <= number; i++) {
        answer.push(cal(i));        
    }
    
    return answer.map(a => {
        if (a > limit) return power;
        return a;
    }).reduce((acc, cur) => acc += cur, 0);
}

---

결론

제곱근을 활용한 약수의 갯수를 구하는 방법으로 할 경우 문제를 해결 할 수 있다.