[Programmers] 기사단원의 무기(Level. 1)

문제설명

https://school.programmers.co.kr/learn/courses/30/lessons/136798?language=python3 

프로그래머스

문제풀이

제출코드

def solution(number, limit, power):
    answer = 0
    list_power = []
    for i in range(1, number+1):
        count = 0
        for j in range(1, int(i**(1/2))+1):
            if i%j == 0:
                count += 1
                if ((j**2) != i) :
                    count +=1
        if count > limit:
            list_power.append(power)
        else:
            list_power.append(count)
    
    answer = sum(list_power)
    
    return answer

• 빈 리스트를 만들어서 1부터 number까지 약수의 개수를 구하고 개수를 리스트(list_power)에 넣어준다. 만약 count가 limit보다 크다면 power를 리스트에 넣는다. 모든 약수의 개수를 구하면 list_power에 있는 값을 모두 더하고 반환한다.
• 약수의 개수를 구할 때 1부터 해당 수까지 모든 수를 확인하게 되면 O(N) 시간복잡도를 가지게 되어 시간초과로 테스트 실패하므로 효율적인 알고리즘이 필요하다. N의 약수를 구할 때는 1부터 N의 제곱근 까지의 수만 0으로 나누어 떨어지는지 확인하면 된다.