[프로그래머스] 약수의 개수와 덧셈

문제 설명

 

문제 풀이

function solution(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        let arr = []
     
        for (let j = 0; j <= i; j++) {
            if(i % j === 0) {
                arr.push(j)
            }
        }
        
        if(arr.length % 2 === 0) {
            answer += i
        } else {
            answer -= i
        }
    }
   
    return answer;
}

하지만 시작 복잡도가 O의 n제곱

 

더 나은 풀이

function solution(left, right) {
    let answer = 0;
    
    for (let i = left; i <= right; i++) {
        // i가 완전 제곱수인지 확인
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;  // 약수의 개수가 홀수인 경우
        } else {
            answer += i;  // 약수의 개수가 짝수인 경우
        }
    }
    
    return answer;
}

시간 복잡도 O의 n