Lv.1_기사단원의 무기

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

프로그래머스

def get_divisor(n):
    divisors = []
    divisors_back = [] 

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

    return len(divisors + divisors_back[::-1])

def solution(number, limit, power):
    l = []
    for i in range(1, number+1):
        l += [get_divisor(i)]
    
    result = 0
    for i in l:
        if i <= limit:
            result += i
        else:
            result += power
    
    return result

내가 푼 풀이

이렇게 풀어야 시간복잡도를 해결할 수 있다

 

만약, 약수 구하는 과정에서

def get_divisor(x):
	count = 0
	for i in range(1, x+1):
    	if x % i == 0:
        	count += 1
	return count

이런식으로 약수의 개수를 구할 수 있겠지만, 

이 방법으로는 시간복잡도를 해결할 수 없다.

 

약수가 대칭 구조를 가지고 있다는 아이디어를 가지고 첫번째 방법으로 약수의 갯수를 구해야 한다.

이 방법을 잘 기억해두자