프로그래머스 > 4. 기사단원의 무기

❓ 문제

프로그래머스 Level 1 연습문제 > 기사단원의 무기

❗ 해결

1. 문제 자체는 간단하므로, 왠지 약수를 구할 때의 효율성을 볼 것 같았다. 10이라는 숫자가 주어지면, 1부터 10까지 나눠보면서 약수를 구하면 모든 경우의 수를 다 나눠보므로 시간복잡도는 O(N)이 된다. 따라서 N이 아주 큰 수 (1억 이상)가 나오게 되면 시간 초과로 풀 수 없게 될 것 같았다.

function findNumDivisor(num) {
    result = [];
 
    for (let n = 1; n <= num; n++){
        cnt = 0;
        for (let d = 1; d <= n; d++) {
            if (n % d === 0) {
                cnt++;
             
            }
        }
        result.push(cnt);
    }
    return result;
}


function solution(number, limit, power) {
    const numArray = findNumDivisor(number);
    
    let sum = 0;
    for (let i = 0; i < numArray.length; i++) {
        if (numArray[i] > limit) {
            sum += power;
        }
        else {
            sum += numArray[i];
        }
    }
    
    return sum;
}

결과적으로 보기 좋게 시간초과로 실패했다.
조금 더 효율적인 방법을 사용해야 했다.

2. 어차피 약수를 구할때는 n이 주어지면 n / 2까지만 해서 약수를 구하면 시간초과가 나지 않을 것이라고 생각했다.

따라서 약수를 찾는 코드를 수정했다.

function findNumDivisor(num) {
    result = [];
    
    for (let n = 1; n <= num; n++){
        cnt = 0;
        for (let d = 1; d <= n / 2; d++) {
            if (n % d === 0) {
                cnt++;
            }
        }
        result.push(cnt + 1);
    }
    return result;
}

function solution(number, limit, power) {
    const numArray = findNumDivisor(number);
    let sum = 0;
    for (let i = 0; i < numArray.length; i++) {
        if (numArray[i] > limit) {
            sum += power;
        }
        else {
            sum += numArray[i];
        }
    }
    
    return sum;
}

시간은 확 줄었지만 여전히 실패했다.
도저히 방법을 모르겠어서 구글의 힘을 빌리기로 했다.

그 결과 여러 블로그에서는 약수를 구하는 방법을 크게 세가지로 설명을 하였는데 첫번째는 내가 사용했던 방법 즉 모든 수를 다 나눠보는 것.
두 번째는 어떤 수가 주어지면, 그 수의 2를 나눈 수까지만 약수를 구하면 된다는 것.
그리고 마지막으로 방법 한가지가 더 있었다.

3. N의 약수를 구할 때, 1부터 N의 제곱근 까지의 수만 나누어 본다.
   참고 : https://kbw1101.tistory.com/32

욱파카 님의 블로그를 참고하여 공부하면서 한번 더 적어보았습니다.

예를 들면, N이 100이라고 가정을 하면 1부터 N의 제곱근, 즉 10까지만 나누어본다.
그렇게 되면
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의 약수가 된다.
그리고, 구해진 약수로 다시 나눈다.

100 % 1 = 100
100 % 2 = 50
100 % 4 = 25
100 % 5 = 20
100 % 10 = 10

이렇게 나누게 되면 추가로 약수를 얻을수 있다.
중복을 제거하고 리스트에 추가하게 되면 1,2,4,5,10,100,50,25,20 이 우리가 구하는 약수가 된다.

이렇게 되면 시간복잡도가 O(√N)이 된다는 걸 알았다.

그래서 코드를 다시 수정하였다.

function findNumDivisor(num) {
    result = [];
    
    for (let n = 1; n <= num; n++){
        cnt = 0;
        for (let d = 1; d <= Math.sqrt(n); d++) {
            if (n % d === 0) {
                cnt++;
                if (n / d != d) {
                    cnt++;
                }
            }
        }
        result.push(cnt)
    }
    return result;
}

function solution(number, limit, power) {
    const numArray = findNumDivisor(number);
    
    let sum = 0;
    for (let i = 0; i < numArray.length; i++) {
        if (numArray[i] > limit) {
            sum += power;
        }
        else {
            sum += numArray[i];
        }
    }
    
    return sum;
}

먼저 findNumDivisor에 num을 매개변수로 받는다.
그리고 약수의 개수를 담을 배열 하나를 선언해준다.

1부터 num까지의 약수의 개수를 구할려고 첫번째 반복문을 돌린다.
count 변수는 0으로 초기화한다.
그리고 두번째 반복문에서는 해당 숫자의 약수의 개수를 구하는데 1부터 n의 제곱근 까지만 반복문을 돌린다.
만약 n이 d로 나누어 떨어진다면, 해당 숫자는 약수이므로 count를 1 증가시킨다.
그리고, 중요한 부분인데 만약 n을 d로 나누었을 때 d와 다르다면, 두 번째 약수를 찾은 것이므로 count를 1 증가시키고,
반복문이 끝났으면 count를 배열에 담고, count를 0으로 초기화한 후 다시 반복문을 돌린다.

그렇게 돌면서 얻은 배열을 구하고, sum이라는 변수를 0으로 초기화한다.
마지막으로 배열을 반복하면서 제한수치를 초과한 경우엔 제한 수치를 더해주고, 초과하지 않은 경우에는 공격력을 더해준 후 return 해준다.