코딩테스트 | (JavaScript) 프로그래머스 : 약수의 개수와 덧셈

✅문제

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

❕ 제한사항

• 1 ≤ left ≤ right ≤ 1,000

🎹📢입출력 예제

✍풀어보기

function getNumberOfFactors(n) {
    let m = 1, count = 0;
    while(n >= m) {
        if (n % m === 0) count++;
        m++;
    }
    return count;
}

function solution(left, right) {
    let answer = 0;
    for (let i = left; i <= right; ++i) {
        if (getNumberOfFactors(i) % 2 === 0) {
            answer += i;
        } else {
            answer -= i;
        }
    }
    return answer
}

쉽고 빠르게 풀었지만, 속도 효율이 안나와서 불필요한 연산이 있나 고민을 했다. 그리고 소수의 개수를 더 효율적으로 찾는 방법을 검색해보았다.

소인수분해와 거듭제곱의 수를 이용하여 소수의 개수를 쉽게 구할 방법을 찾았지만 소인수분해하여 나온 결과 값의 거듭제곱을 이용하는 방법으로 위의 코드보다 효율성이 좋지 않았다. 그래도 간단하게 방법을 설명하자면 예를 들어 512의 약수의 개수를 구하여 소인수분해하면 2의 9제곱(2^9)이다. 9+1을 하면 10인데 이것이 512의 약수의 개수다. 72를 소인수분해하면 2³x3² = (3+1)x(2+1) = 4x3 = 12 즉 72의 약수의 개수는 12개이다.

🎈다른 사람의 풀이

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

이렇게 효율적으로 풀 줄이야~ 놀라웠다. 제곱근이 정수라면 약수의 개수가 홀수라는 것이다. 수학적 지식을 응용하여 정말 잘 이용했다고 생각한다. 멋지다!

---

참고 자료 및 사이트 (감사합니다)

• https://programmers.co.kr/learn/courses/30/lessons/77884
• 소인수분해로 약수의 개수 구하기