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

 

문제 풀어보기: https://school.programmers.co.kr/learn/courses/30/lessons/12928

 

풀이 보기
더보기
function solution(n) {    
   let nums = [];
    
   for(let i = 1; i <= n; i++) {   
       if(n % i === 0) nums.push(i);
   }
    
   let sum = nums.reduce((acc, curr) => 
        acc + curr, 0);
    
    return sum;
}

이 문제는 너무 쉽지만 단순히 푸는 것이 아닌 시간복잡도를 고려해야 한다.

위의 코드도 정답이긴 하지만, 만약 n이 엄청 큰 숫자라면 1부터 n까지 반복을 해야 하기 때문에 시간복잡도가 커지게 된다.

나는 reduce를 사용하고 싶어서 저렇게 했지만 더 간단하게 작성할 수도 있다!

 

function solution(n) {    
   let sum = 0;
    
   for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            sum += i;
            if (i !== n / i) sum += n / i;
        }
    }
    
    return sum;
}

 이 코드는 시간복잡도를 개선한 코드이다.

약수는 짝을 이루는 특징이 있기 때문에 그 특징을 활용하면 된다!

만약 i가 n의 약수일 경우, n / i도 약수이기 때문에 제곱근을 활용해서 i의 범위를 좁혀준다.

 

따라서 위의 코드처럼 실행한다면 먼저 1부터 제곱근까지의 수에서 약수를 탐색하여 더해주고,

탐색한 약수의 짝꿍을 찾아서 그 수도 더해준다.

여기서 i가 중복되지 않게 i !== n / i 조건도 넣어줘야 한다.

 

n이 큰 수가 아니라는 가정일 때는 첫 번째 코드를 사용하는 것이 좋을 수도 있을 것 같다. 

 

+ Recent posts