♡̈ 14. 프로그래머스:: 약수의 합

 

약수를 어떻게 구해야할까.

 

반복문 i를 늘려가며,

% 연산자가 0에 만족하는 것만 따로 빼주면 되지 않을까?

 

그래서 약수를 찾는 단계와 합산하는 단계로 나누었다.

1. 약수 찾기
 - 순회하며 해당 정수가 n의 약수인지 확인
 - n이 정수로 나누어떨어지면 n의 약수
2. 약수 합산
 - 조건에 충족할 때마다 if문으로 합산

function solution(n) {
    let sum = 0;

    for (let i = 1; i <= n; i++) {
        if (n % i === 0) {
            sum += i;
        }
    }

    return sum;
}

 

전반적으로 이렇게 문제를 푼거보면,

약수를 찾을 때 더 간단한 메서드는 없이 보통 반복문으로 푸는 듯하다.

 

다만, 이러한 문제의 유형에

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

 

이런 식으로

Math.sqrt(n)

이 메서드를 많이 볼 수 있는데 잘 이해가 안됐다.

 

sqrt는 제곱근을 반환해주는데, 약수랑 무슨 관련인지 모르겠어서 그 부분을 찾아 정리했다.

 

Math.sqrt(n)가 약수 찾기와 관련이 있는 이유는 그 과정을 최적화할 수 있기 때문이다.

'n'의 약수는 대칭성을 가진다.

 

36을 기준으로 삼아보자.

1 * 36
2 * 18
3 * 12
4 * 9
6 *6

 

이처럼 약수는 쌍으로 나타나기 때문에, n을 제곱근까지 순회하면 그 과정을 최적화할 수 있다는 것이다.

예를 들어 36의 제곱근은 6이며, 6까지만 순회하면 결과값이 나온다는 것.

 

이런 식의 방식은 생각하지 못했는데 Math.sqrt를 통해 확실히 더 최적화할 수 있게 됐다.