[프로그래머스] 약수의 개수와 덧셈 - level 1 (javascript)

프로그래머스

 

|  제출

function solution(left, right) {
    let sum = 0;
    
    for(let i = left; i <= right; i++){
        let divisor = [];
        for(let j = 1; j <= i; j++){
            if(i % j === 0) divisor.push(j);
        }
        divisor.length % 2 === 0 ? sum += i : sum -= i;
    }
    
    return sum;
}

 

|  풀이과정

left부터 right까지의 숫자를 i라고 하자. i를 1부터 i까지 나누었을 때, 나누어 떨어진다면 그 수는 약수이다.

약수를 divisor 배열에 저장해놓고, 배열의 크기에 따라 해당하는 i를 sum에 더하거나 빼주면 된다.

내가 푼 방식은 모든 경우의 수를 따져봐야해서 시간 복잡도가 O(N)으로 효율적인 코드는 아니었다.

 

다른 사람 풀이

function solution(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}

주어진 숫자의 제곱근이 정수면 약수의 개수가 홀수라는 것을 이용해 푼 풀이이다.

예를 들어, 64의 약수는 [1, 2, 4, 8, 16, 32, 64]로 7개이다.

제곱근이 정수가 아니라면 모든 약수들은 짝이 있기 때문에 약수의 개수는 짝수가 나온다.