연습문제 > 기사단원의 무기

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

 

일단 약수의 개수를 구하는 함수를 활용해서 풀어보려고 한다

 

function count(n) {
    let p = 0;
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) p++;
    }
    return p;
}

이제 이 함수를 변형해서 limit 의 제한 보다 약수의 갯수 p가 초과 될 경우 정해진 power 를 리턴하는 함수로 변경

function buy(n, limit, power) {
    let p = 0;
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) p++;
    }
    return p > limit ? power : p;
}

그리고

결과값을 리턴할 수 있도록 기사단원의 수 number를 순차 계산하는 함수 만들기

function solution(number, limit, power) {
    let result = 0;
    for (let j = 1; j <= number; j++) {
        result += buy(j, limit, power);
    }
    return result;
}

모두 잘 풀리긴 하지만

제한사항 1 <= number <= 100,000 에서 시간초과가 걸려버림

for 문이 2개라서 O(N^2) 이 되어서 생긴 문제 같음

 

이걸 축약해서 O(N)으로 만들어야 통과되는 문제인 것이다

약수의 개수를 구할 때 더 효율적으로 걸러내는 방식을 써야하는데

여기서는 또 GPT의 힘을 빌어서 풀어 본다

O(N)까지는 힘들어도 O(N log N) 까지는 가능한 것 같다

function solution(number, limit, power) {
    let divisors = new Array(number + 1).fill(0);
    for (let i = 1; i <= number; i++) {
        for (let j = i; j <= number; j += i) {
            divisors[j]++;
        }
    }

    let result = 0;
    for (let i = 1; i <= number; i++) {
        result += divisors[i] > limit ? power : divisors[i];
    }
    return result;
}

왜 for 문이 3개인데 쟤는 통과되지? ㅜㅜ

 

약수의 개수 구하는 방법에 문제가 있는 것을 깨닫고

제곱근을 활용한 좀 더 효율적인 약수 개수 구하기 알고리즘을 찾음

function countDivisors(n) {
    let count = 0;
    for (let i = 1; i * i <= n; i++) {
        if (n % i === 0) {
            // i가 n의 약수일 때
            if (i * i == n) {
                // i와 n/i가 같은 경우 (n이 완전제곱수인 경우)
                count += 1;
            } else {
                // i와 n/i가 다른 경우
                count += 2;
            }
        }
    }
    return count;
}
 

 

이걸 활용해서 

 

function buy(n, limit, power) {
    let p = 0;
    for (let i = 1; i * i <= n; i++) {
        if (n % i === 0) {
            // i가 n의 약수일 때
            if (i * i == n) {
                // i와 n/i가 같은 경우 (n이 완전제곱수인 경우)
                p += 1;
            } else {
                // i와 n/i가 다른 경우
                p += 2;
            }
        }
        if (p > limit) {
            return power;
        }
    }
    return p;
}

function solution(number, limit, power) {
    let result = 0;
    for (let j = 1; j <= number; j++) {
        result += buy(j, limit, power);
    }
    return result;
}

 

이렇게 푸니까 해결!

알고리즘은 어려워