[프로그래머스 LV1] 약수의 개수와 덧셈 - 완전제곱수

https://school.programmers.co.kr/learn/courses/30/lessons/77884

 

문제 설명

 

두 정수 `left`와 `right`가 매개변수로 주어집니다. `left`부터 `right`까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 `solution` 함수를 완성해주세요.

 

제한사항

• 1 ≤ left ≤ right ≤ 1,000

입출력 예

left	right	result
13	17	43
24	27	52

 

시도한 방식

첫 풀이는 약수의 개수를 구하고 짝수인지 홀수인지 판단했었습니다.

function solution(left, right) {
    var answer = 0;

    for (let i = left; i <= right; i++){
        let count = 0;
        let index = 1;

        while (index <= i) {
            if (i % index === 0) count++
            index++
        };

        if (count % 2 === 0) answer += i;
        else answer -= i;
    }

    return answer
}

 

하지만 완전제곱수 개념을 활용하면 더 간단하게 풀 수 있었습니다.

 

완전제곱수와 약수의 개수

완전제곱수는 어떤 정수를 제곱한 수입니다(e.g. 1, 4, 9, 16 등). 완전제곱수의 특징 중 하나는 그 약수의 개수가 홀수라는 점입니다.

이는 완전제곱수의 약수들이 대칭을 이루어 짝을 이루지만, 정확히 제곱근에 해당하는 약수는 그 짝이 없기 때문입니다 (예를 들어, 16의 약수는 1, 2, 4, 8, 16이고, 여기서 4는 유일한 홀수 약수입니다).

따라서, 각 숫자가 완전제곱수인지 아닌지만 판별하면, 그 숫자의 약수의 개수가 홀수인지 짝수인지 쉽게 알 수 있습니다.

`Number.isInteger(Math.sqrt(x)) == true` 인 경우 x의 약수의 개수는 홀수인 셈입니다.

 

해결한 풀이

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;
}

 

Number.isInteger()

`Number.isInteger` 함수는 해당 숫자가 정수인지 아닌지를 판별해주는 함수입니다.

 

Math.sqrt()

`Math.sqrt` 함수는 숫자의 제곱근을 반환해주는 함수입니다.