[프로그래머스] lv1. 약수의 합 / Javascript

[프로그래머스] lv1. 약수의 합 / Javascript

 

1. 문제

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

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

 

제한 사항 

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

 

입출력 예 #1

12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.

 

입출력 예 #2

5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.

 

프로그래머스

 

2. 풀이

function solution(n) {
    let result = [];
    let total = 0;
    
    for (let i=1; i<=Math.sqrt(n); i++) {
        if (n % i === 0) {
            result.push(i);
        }
    }
    
    result.forEach((v) => {
        const opV = n / v === v ? 0 : n / v;
        total += (v + opV)
    })

    return total;
}

 

핵심 아이디어

1. 12의 약수는 [1,2,3,4,6,12] 이다. 사실 이는 반으로 쪼개도됨 [1,2,3] [4,5,6]

1,2,3만 구하고 나머진 N에서 1,2,3으로 각각 나누면 4,5,6을 구할 수 있음. 단순해보이지만 시간복잡도에서 큰 차이가 있음. 

2. 16같은 수는 [1,2,4,8,16] 약수를 가진다. 보면 약수의 개수가 홀수임. 이때는 √n 까지 순회하여 나누어떨어지는 값을 배열에 넣어두고 

이후 연산에서 값이 √n일 경우 예외처리 해주면 됨. 이는 O(n)에서 O(√n) 으로 시간복잡도를 줄일 수 있음.

 

 

 

 

 

4. 시간복잡도

O(√n)

 

→ 따라서 최악의 경우에도 O(√3000) = O(54.xx)