[Level 1] [python] 기사단원의 무기

문제

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

파이썬 풀이

def getMyDivisorLen(n):

    divisorsList = []

    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            divisorsList.append(i) 
            if ( (i**2) != n) : 
                divisorsList.append(n // i)
    
    return len(divisorsList)

def solution(number, limit, power):
    answer = 0
    
    for i in range(1, number+1) :
        divisorLen = getMyDivisorLen(i)
        if divisorLen > limit :
            answer += power
        else :
            answer += divisorLen
    return answer

우선 약수의 개수를 구하는 함수를 getMyDivisorLen함수로 구현하였다.

시간 복잡도를 줄이기 위해 for문으로 n까지의 수를 도는 것이 아니라 약수에는 곱셈의 짝이 있다는 원리를 이용하여 n의 절반까지만 for문으로 반복하였다.

만약에 n이 i로 나누어진다면 i와 함께 곱셈의 짝인 n을 i로 나눴을 때의 값을 추가로 넣어준다.

단 if문에서 알 수 있듯 만약 n이 i의 제곱이라면 i가 중복으로 약수 배열에 들어가기 때문에 이는 제외하고 넣어 주었다.

그러고 우리는 약수의 모음이 아닌 약수의 수만 사용하므로 약수 배열의 길이를 반환하였다.

 

본 프로그램에서는 기사단원 한명씩 for문으로 돌면서 약수의 개수를 구하였고, 

약수의 수가 limit보다 크다면 제한 수치인 power을 결괏값에 더하고

아니라면 함수에서 구한 약수의 수를  결과값에 더하였다.