[프로그래머스] 기사단원의 무기 (JS) (+ 약수 구하는 최적의 알고리즘)

기사단원의 무기: 약수 구하는 최적의 알고리즘

 

이 문제는 기사들이 자신의 번호에 해당하는 약수의 개수만큼의 공격력을 가진 무기를 구매하는 문제입니다.

또한, 특정한 제한 수치 이상의 공격력을 가지게 되는 기사는 대체 공격력을 가진 무기로 변경해서 구매해야합니다. 

즉! 각 기사의 무기 공격력을 구하고, 이를 모두 합산하여 무기 제작에 필요한 철의 총 무게를 구하는 것이 답입니다.

---

 

1. 문제 해결을 위한 주요 단계

• 약수 개수 계산: 각 기사 번호의 약수를 구하는 방법을 이용해, 각 번호에 해당하는 약수의 개수를 구합니다.
• 제한 조건 처리: 약수의 개수가 주어진 제한 수치보다 큰 경우, 대체 공격력을 적용합니다.
• 합산: 모든 기사의 공격력(즉, 약수의 개수 또는 대체 공격력)을 합산하여 최종 결과를 반환합니다.

---

 

2. 해결 과정

1. 약수의 개수 구하기

이 문제에서는 다른 것보다 약수 구하기 과정에서 시간 복잡도를 줄이는 것이 매우 중요합니다.

저는  제곱근을 이용한 약수 구하기 방법을 사용하여 시간 복잡도를 줄였습니다. 

 

 

1. 일반적인 약수 구하기 방법

 

가장 직관적인 약수 구하기 방식은 1부터 n까지의 모든 수를 대상으로 n을 나누어 약수가 되는지를 확인하는 것입니다.

즉, n % i === 0인 i를 모두 찾는 방식입니다. ((사실상 노가다)) 

 

일반적인 방법의 코드

const factors = (number) => {
    let count = 0;
    
    // 1부터 number까지 반복문을 돌며 약수 확인
    for (let i = 1; i <= number; i++) {
        if (number % i === 0) {
            count++;
        }
    }
    
    return count;
}

 

이 방식의 시간 복잡도는 O(n)입니다. 그러다보니 n이 커질수록 1부터 n까지의 모든 수를 확인해야 하므로 매우 비효율적입니다.

예를 들어, n = 100,000인 경우, 최대 100,000번의 나눗셈 연산을 해야 합니다. 그러다보니 시간 초과가 나올 수 있습니다. 

 

 

2. 제곱근을 이용한 최적화 방법

약수의 특성상, 약수는 항상 쌍을 이루어 존재합니다.

 

예를 들어, 36의 약수는

1 × 36,

2 × 18,

3 × 12,

4 × 9,

6 × 6과 같이 쌍을 이룹니다.

 

즉, 약수 중 한 값이 i라면, 다른 값은 n / i 이게 되는 겁니다. 

이때, 제곱근보다 큰 약수는 이미 작은 약수에서 계산이 완료된다는 점을 이용하여, 제곱근까지만 확인하면 약수를 모두 구할 수 있습니당. 

 

제곱근을 이용한 방법의 코드

const factors = (number) => {
    let count = 0;
    
    // number의 제곱근까지만 반복하면서 약수 확인
    // 예시: number 36 일때 
    for (let i = 1; i <= Math.sqrt(number); i++) { // Math.sqrt(36) == 6;
        if (number % i === 0) {
            // 조건 통과한 i == [1, 2, 3, 4, 6]
            count++;  // i는 약수
            if (i !== number / i) {
            	// i 와 number / i 
                // [[1, 36], [2, 18], [3, 12], [4, 9] , [6, 6]]
                // [6, 6] 은 동일한 숫자여서 카운트 안됨 
                count++;  // number / i도 약수
            }
        }
    }
    
    return count;
}

 

이 방식의 시간 복잡도는 O(√n)입니다. n의 제곱근까지만 확인하면 되므로, 매우 큰 수를 대상으로도 연산을 효율적으로 수행할 수 있습니다. 예를 들어, n = 100,000이라면 제곱근인 약 316까지만 확인하면 되므로, 최대 316번의 연산만으로 약수를 구할 수 있습니다.

 

2. 제한 조건에 따른 공격력 설정

각 기사의 약수 개수가 제한 수치를 초과하면 해당 기사는 대체 공격력을 사용합니다. 따라서 약수 개수를 구한 후, 그 값이 제한 수치보다 큰지 확인하고, 초과하는 경우에는 대체 공격력을 적용합니다.

3. 총 철의 무게 계산

모든 기사의 공격력을 합산하여 필요한 철의 총 무게를 구합니다. 공격력 1당 1kg의 철이 필요하므로, 모든 기사의 공격력을 단순히 더하면 됩니다.

 

---

3. 코드 구현

// 특정 숫자의 약수 개수를 구하는 함수
const factors = (number) => {
    let count = 0;
    
    // 제곱근까지만 반복하면서 약수를 계산
    for (let i = 1; i <= Math.sqrt(number); i++) {
        if (number % i === 0) {
            count++;  // i는 약수
            if (number / i !== i) count++;  // number / i도 약수일 경우 추가
        }
    }

    return count;  // 약수의 총 개수 반환
}

// 문제 해결을 위한 solution 함수
function solution(number, limit, power) {
    let answer = 0;
    
    // 1부터 number까지 각 기사의 약수 개수를 구하고 처리
    for (let i = 1; i <= number; i++) {
        let num = factors(i);  // 약수의 개수 구하기
        if (num > limit) num = power;  // 제한 수치를 초과하면 대체 공격력 적용
        
        answer += num;  // 공격력을 총합에 더함
    }
    
    return answer;  // 무기 제작에 필요한 총 철의 무게 반환
}

 

 

 

이 문제는 효율적으로 약수를 구하는 과정 빼고는 매우 쉽게 해결 가능한 문제였습니다.

저도 이 문제 전에는 약수를 구하는 과정을 일반적인 과정으로 진행했었는데 이 문제 덕분에 이후에 또 약수 관련 문제가 나오면 이와 같은 효율적으로 약수 구하는 방식을 택할거 같습니다.