기사단원의 무기

 

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

프로그래머스

문제풀이

해당 조건에서 약수를 구하려면 이중 반복문을 이용한 방법외에는 없다. 다만 최대 수행횟수 10만 * 10만은 일백억이라는 실행횟수가 나오기에 시간복잡도가 O(n^2)이 되어버리며 일반적인 방법으로는 처리가 불가능하다.

그렇다면 n의 제곱근 만큼 반복하며 약수의 개수를 구하여 반환 한다면 시간복잡도는 O(n log n)이 된다.

def solution(number, limit, power):
    answer = 0

    for i in range(1, number + 1):
        temp = divisors(i)
        if temp > limit:
            answer += power
        else:
            answer += temp

    return answer


def divisors(n):
    total = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            # i가 n의 약수이면, n/i도 약수이므로 2를 더함
            total += 2 if i != n // i else 1

    return total

 

하지만 여기서 더 최적화를 한다면 어떨까? 에라스토테네스의 체 알고리즘를 응용할 수 있다.

 

개선된 코드

def solution(number, limit, power):
    answer = 0
    cache = divisors(number)  # 모든 숫자에 대한 약수 개수 미리 계산

    for i in range(1, number + 1):
        temp = cache[i]
        if temp > limit:
            answer += power
        else:
            answer += temp

    return answer


def divisors(n):
    total = [0] * (n + 1)

    for i in range(1, int(n**0.5) + 1):
        for j in range(i * i, n + 1, i):  # i의 배수들에 대해 약수 개수를 증가
            total[j] += 2 if i * i != j else 1

    return total