최고의 개발자 (목표)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/77884?language=javascript 

입출력

코드

function solution(left, right) {
    let answer = 0; 
    // left 부터 right 까지의 수들의 약수 개수 구하기
    for(let i = left; i <= right; i++){
        let count = 0; // i의 약수 개수를 저장
        
        // j는 1부터 i의 제곱근까지의 수
        // j가 i의 약수인지 확인
        for(let j = 1; j <= Math.sqrt(i); j++){
            if(i % j === 0) { // i가 j로 나누어 떨어지면 약수이다.
                count++;
                if(i / j != j) count++; // i = 25, j = 5의 경우 5를 2번 세면 안됨.
            }
        }
        // 약수의 개수가 짝수면 더하고 홀수면 빼기
        count % 2 === 0 ? answer += i : answer -= i;
    }
    return answer;
}

풀이

left와 right 사이에 있는 수들의 약수 개수를 구하고, 그 개수가 짝수면 더하고 홀수면 빼면 된다.

1. 반복문으로 left에서 right까지 돌면서 i의 약수 개수를 구해준다. count는 i의 약수 개수를 저장할 변수이다.

2. j를 1부터 i의 제곱근까지 확인하면서 i의 약수인지 확인하고, i가 j로 나누어 떨어지면 약수이므로 count++ 해준다.

이때, i의 끝까지 확인하는 것이 아니라 i의 제곱근까지만 확인하는 이유는 굳이 끝까지 확인하지 않아도 되기 때문이다. 물론 다 확인해서 약수를 구해도 답을 구할 수 있다.

예를 들어, i = 25라고 해보자.

25의 약수는 1 5 25 이다.

방법 1) 1부터 끝까지 확인하는 방법

1부터 25까지 돌면서 25 % 1 === 0 , 25 % 2 === 0, ... 25 % 25 === 0 을 확인해 count++를 해준다.

-> 3개가 나온다.

방법 2) 1부터 i의 제곱근인 5까지 확인하는 방법(에라토스테네스의 체)

25 % 1 === 0, 25 % 2 === 0, 25 % 3 === 0, 25 % 4 === 0, 25 % 5 === 0 을 확인한다.

나누어 떨어진다면 i의 약수이다. 그러나 제곱근까지만 확인했기 때문에 count를 한 번 더 세주어야한다. 1 x 25 = 25이므로, 1도 25의 약수이고 25도 25의 약수가 된다. 따라서 1을 세줄 때, 25도 같이 세어주어야한다.

5가 약수인지 판단했을 때, 25 % 5 는 0이어서 약수로 판명이 된다. 

이때 5의 경우에는 한 번만 세주어야 하므로(5 x 5 = 25), i / 5 == 5 인 경우에는 세어주면 안된다.

따라서 i / j != j 인 경우에만 count를 한 번 더 세어주었다. i != j * j 와 같은 식이다.

구한 i의 약수의 개수가 짝수면 answer에 더해주고, 홀수면 빼주었다.