1Level / 월간 코드 챌린지 시즌2 / 약수의 개수와 덧샘

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서,

약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를

return 하도록 solution 함수를 완성해주세요.

 

 

제한 사항

• 1 ≤ left ≤ right ≤ 1,000

 

문제 풀이 방법

• 문제의 알고리즘을 완전탐색으로 생각하여 이중 for문을 이용해 코드를 작성했다.
• count라는 변수를  for문 안에서 선언하여 약수의 개수를 측정하는 데에 사용했다.
• 그리고 2로 나누었을 때 나머지가 0이면 약수가 짝수개, 0이 아니면 홀수개라는 로직으로계산했다.

 

내가 작성한 코드

function solution(left, right) {
    let answer = 0;
    for(let i=left; i<=right; i++){
        let count = 0;
        for(let j=1; j<=i; j++){
            if(i % j === 0){
                count += 1;
            }
        }
        if(count % 2 === 0){
            answer += i;
        }
        else{
            answer -= i;
        }
    }
    return answer;
}

 

 

문제를 푼 뒤 다른 사람이 작성한 코드를 보고 놀랐다.....

바로 이 코드인데

function solution(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}

이 코드에서 주목해야 할 부분은

if (Number.isInteger(Math.sqrt(i)))

이 조건문 이다.

 

로직은 제곱근이 정수이면 약수의 개수가 홀수라는 것이다.

 

예를 들어보자

먼저 12라는 수를 i에 넣어보자

제곱근은 3.4641... 이며,

약수는 1, 2, 3, 4, 6, 12 이렇게 6개이다.

 

다른 예로 9를 보자

제곱근은 3이며,

약수는 1, 3, 9 이렇게 3개이다.

 

좀 더 스마트하게 생각하면 기발한 코드가 나올 수 있다.

 

위의 코드는 완전 탐색 알고리즘을 이용했다고 말 할 수 있는가?

내 생각은 할 수 있다고 생각한다.

우선 left에서 right까지의 모든 수를 탐색했고,

그 수들 중 약수의 개수가 짝수인 수와 홀수인 수를 구분했기에

완전 탐색 알고리즘을 사용했다고 생각한다......

 

아직 초짜가 생각하는거라 틀릴지도 모르겠다....