[프로그래머스 Level 1] 약수의 합

---

문제 설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한 사항

• n은 0 이상 3000이하인 정수입니다.

입출력 예

n                    return

12	28
5	6

---

이 문제는 비교적 해결하기 쉬운 문제였지만, for문의 반복 범위를 고려하지 않으면 시간초과로 실패할 수 있는 문제이다. 해답은 [프로그래머스 Level 1] 소수찾기와 동일하다.

어떤 수 n은 n의 제곱근 이하의 수와 그 이상의 수의 곱으로 표현이 가능하다. 그러므로 i를 n의 제곱근까지만 반복해주면 이 문제를 시간복잡도 O(root n)으로 해결 가능하다.

 

function solution(n) {
    var factor = new Set();
    if(n == 0){
        return 0;
    }

    for(var i = 1; !factor.has(i) && i <= Math.sqrt(n) ; i++){
        if(n % i == 0){
            factor.add(i);
            factor.add(Math.floor(n / i));
        }
    }
    var answer = 0;
    factor.forEach(item => answer += item)
    return answer;
}

 

처음엔 배열을 사용해서 push를 통해 약수를 factor에 추가했는데, n이 제곱수인 경우에 동일한 수가 두 번 들어가는 실수를 범하게 된다. 그래서 동일한 원소를 가지지 않는 Set을 이용해서 해결했다.