[프로그래머스] JS - 약수의 개수와 덧셈

문제

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ left ≤ right ≤ 1,000

입출력 예

left	right	result
13	17	43
24	27	52

나의 풀이

function solution(left, right) {
    var answer = 0;
    let array = [];
    
    for(let i = left; i <= right; i++) {
        array.push(i);
    }
    
  	// array[i] 값의 약수를 찾는다.
    for (let i = 0; i < array.length; i++) {
     	// 중복 제거를 위한 new Set사용  
      	let mySet = new Set(); 
        // 제곱근을 이용한 약수 구하기 알고리즘
      	for (let j = 1; j <= Math.sqrt(array[i]); j++) {
            if (array[i] % j === 0) {
                mySet.add(j);
                mySet.add(array[i] / j);
            }
        }
      	// 약수의 개수가 짝수이면 + 홀수이면 -
        if(mySet.size % 2 === 0) {
            answer += array[i]
        } else {
            answer -= array[i]
        }
    }
    
    return answer;
}

약수를 구하는 알고리즘

1. 모든 수를 나눠서 약수 구하기

: 가장 단순한 방법으로 10의 약수를 구한다면 1~10까지의 숫자로 나누었을 때 나머지가 0인 숫자가 10의 약수가 된다.

const n = 10;
const array = [];
for(let i=1; i<=10; i++){
    if(n % i === 0) {
        array.push(i);
    }
};
// [1, 2, 5, 10] 10의 약수들.

간단하지만, 모든 경우를 탐색하므로 O(n)의 시간 복잡도를 가지게 된다.

2. 주어진 N의 절반을 대상으로 약수 확인하기

: 약수는 자신을 제외하고 N/2보다 클 수 없다는 사실을 이용한 방법

const n = 10;
const array = [];
for(let i=1; i<=10/2; i++){
    if(n % i === 0) {
        array.push(i);
    }
};
console.log([...array, n]);
// [1, 2, 5, 10]

1번과 같은 방법이지만 탐색의 수를 절반 줄일 수 있다.

3. 제곱근(Math.sqrt)을 이용한 방법 👍

: N의 약수는 1부터 N의 제곱근 까지의 수만 나머지가 0인 경우를 확인하면 된다.
N = 100인 경우 N의 제곱근은 10이다. 1부터 10까지만 나머지가 0인 경우를 보자.

• 100 % 1 = 0
• 100 % 2 = 0
• 100 % 3 = 1
• 100 % 4 = 0
• 100 % 5 = 0
• 100 % 6 = 4
• 100 % 7 = 2
• 100 % 8 = 4
• 100 % 9 = 1
• 100 % 10 = 0

이 경우 [1,2,4,5,10] 이 100의 약수가 되며 N(100)을 이 약수들로 나눈 값들 또한 100의 약수가 된다.

• 100 / 1 = 100
• 100 / 2 = 50
• 100 / 4 = 25
• 100 / 5 = 20
• 100 / 10 = 10

100의 약수는 [1,2,4,5,10,100,50,25,20,10]이 되며, sort나 new Set 메소드들 을 이용하여, 정렬, 중복제거 후 다양하게 이용 할 수 있다.

const N = 100;
let mySet = new Set();
for(let i=1; i<=Math.sqrt(N); i++) {
    if(N % i === 0) {
        mySet.add(i);
        mySet.add(N / i);
    }
}
// mySet {1,100,2,50,4,25,5,20,10}

제곱근을 이용하여 약수를 구하는 경우 시간 복잡도 O(√N)으로 효율성을 높일 수 있다.

+) 다른 사람 풀이

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

제곱근이 정수면 약수의 개수가 홀수다...