[코딩테스트] 프로그래머스 기사단원의 무기 파이썬(Python)

 

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

프로그래머스

import math
def solution(number, limit, power):
    len_divisors = []
    result = 0
    for n in range(1, number+1):
        len_divisors.append(get_len_divisor(n))
    for a in len_divisors:
        if a <= limit:
            result += a
        else:
            result += power
    return result
def get_len_divisor(n):
    result = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            result.append(i)
            if (i ** 2) != n:
                result.append(n // i)
    return len(result)

풀이는 문제에서 조건에 맞추어 구현 하였습니다.

def get_len_divisor(n):
    result = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            result.append(i)
            if (i ** 2) != n:
                result.append(n // i)
    return len(result)

약수의 개수를 구하는 함수를 작성하여 약수의 개수를 구하였습니다.

아래의 블로그를 참고하여 만들었습니다.

[Algorithm/Python] 파이썬 약수 구하기 (시간복잡도 줄여보기)

약수를 구할때 모든 수를 확인하지 않고 주어진 수의 제곱근까지의 수를 확인하며 N = A*B의 특징을 이용한 방법입니다.

 

예를 들어 10의 약수를 구할 때 [1,2,3,4,5,6,7,8,9,10] 모든 수를 확인해가며 약수를 확인하는 방법이 있습니다.

하지만 수가 커지면 그 만큼 시간이 오래 걸리게 됩니다.

 

10의 제곱근 까지의 수([1,2,3])를 구하면 시간을 줄일 수 있습니다.

 

10의 약수는 아래과 같이 표현할 수 있습니다.

10 = (1 * 10) or (2 * 5) 

약수를 구하면 그 약수에 해당하는 짝이 있음을 알 수 있습니다.

따라서 모든 수를 확인하지 않고 제곱근 까지의 수만 확인해도 약수를 구할 수 있습니다.

즉 작은 수의 짝을 찾으면 해당하는 큰 수를 찾을 수 있습니다.

 

또한 25의 약수를 구할 때 5가 두번 들어가는 것을 방지하기 위하여 i ** 2 != n의 조건이 들어간 것을 확인할 수 있습니다.

그리고 25의 제곱근인 5까지만 수를 확인해도 모든 약수를 구할 수 있음을 다시한번 확인할 수 있습니다.

for n in range(1, number+1):
        len_divisors.append(get_len_divisor(n))
    for a in len_divisors:
        if a <= limit:
            result += a
        else:
            result += power
    return result

문제에서 주어진대로 주어진 number까지의 약수의 개수를 구한 뒤에 조건에 맞추어서 값을 추가하여 문제를 해결하였습니다.