기사 단원의 무기

function solution(number, limit, power) {
    let answer = 0;
    for (let i = 1; i<=number; i++) {
        let temp = 0;
        for (let j = 1; j<=i; j++) {
            if (i % j === 0) {temp++}
        }
        temp <= limit ? answer += temp : answer += power
    }
    return answer;
}

문제가 있다.. 시간이 너무 오래걸리는 테스트가 있어서. 수정이 필요하다.

해결

• 시간 복잡도를 줄여야 함.
• 약수 관련 시간복잡도를 줄이기 위해 구글링을 해보고 얻은 힌트

  1. 제곱근까지만 탐색
  2. 제곱근 이상의 약수는 제곱근 이하의 약수에 대응
  3. 제곱근이 정수인 경우 특별히 처리

예시

• 24의 약수를 구할 때, 24의 제곱근은 약 4.9
• 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24
• 제곱근인 4 이하의 약수는 1, 2, 3, 4
• 제곱근 이상의 약수인 6, 8, 12, 24는 각각 4, 2, 4, 1에 대응
• 제곱근인 4는 약수이지만, 4 * 4 = 16이므로 중복 계산되지 않도록 처리

function solution(number, limit, power) {
    let answer = 0;
    for (let i = 1; i<=number; i++) {
        let temp = 0;
        let sqrt = Math.sqrt(i)
        for (let j = 1; j<= sqrt; j++) {
            if (i % j === 0) {temp++
             if (j!==sqrt) {temp++}}
        }
        temp <= limit ? answer += temp : answer += power
    }
    return answer;
}

---

참고
시간복잡도를 줄이는 약수의 합 구하는 알고리즘(Python)