[프로그래머스-Level 1] [JavaScript] 기사단원의 무기 - 약수의 개수 구하기

[문제]

기사단원의 수 numbers, 공격력의 제한 수치 limit, 제한 수치를 초과하는 경우에 제한되는 무기의 공격력을 나타내는 power가 존재합니다. 기사단원의 수가 3일 때, 기사단원1, 기사단원2, 기사단원3이 존재하며 각 기사단원의 약수 개수에 해당하는 공격력을 가진 무기를 구매해야 하며 제한 수치를 초과하는 경우, 제한되는 무기의 공격력이 됩니다. 이 모두를 더한 값을 구하는 것이 문제입니다.

 

[알고리즘] 

제곱근 및 반복문 사용

 

[풀이]

약수의 개수를 구하는 것이 핵심으로 일반 for 반복문을 사용하여 1부터 해당 숫자까지 하나씩 체크해서 구해주는 방법이 물론 가능하지만 시간 초과로 인해 통과하지 못하기 때문에, 이 경우 시간 복잡도를 줄이기 위해 Math.sqrt 제곱근 함수를 사용해서 복잡도를 줄여주면 됩니다. 

 

function solution(number, limit, power) {
    var answer = 0;
    const arr = [];
    
    for (let n = 1; n <= number; n++) {
        let count = 0;
        for (let i = 1; i <= Math.sqrt(n); i++) {
            if (n % i === 0) {
                // 예제 16 / 4 === 4 경우
                // 약수의 개수 1 추가
                if (n / i === i)
                    count++;
                // 16 / 2 === 2는 false 이기 때문에 
                // 2, 8에 해당 되는 약수 2개를 카운트에 더합니다.
                else 
                    count = count + 2;
            }
        }
        arr.push(count);
    }
    
    
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] <= limit)
            answer += arr[i];
        else 
            answer += power;
    }
    
    return answer;
}

 

참조: https://www.geeksforgeeks.org/count-divisors-n-on13/