[프로그래머스] 약수의 합

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

프로그래머스

 

 

자신의 값을 1부터 자기 자신까지의 값으로 나누었을 때, 나머지가 0인 숫자들을 찾아 모두 더해줬다.

그래서 처음엔 다음과 같이 풀었다.

def solution(n):
    sum = 0
    for i in range(1, n + 1):
        if n % i == 0:
            sum += i
            
    return sum

 

하지만 약수를 잘 관찰해보면, 자기 자신의 절반까지만 약수로 정해진다는 사실을 알 수 있다. (자기 자신 제외)

 

12 -> 1, 2, 3, 4, 6, 12
18 -> 1, 2, 3, 6, 9, 18

 

그래서 다음과 같이 코드를 고쳐보았다.

 

def solution(n):
    sum = 0
    for i in range(1, (n // 2) + 1):
        if n % i == 0:
            sum += i
            
    return sum + n

 

이렇게 하면 위 방식의 시간복잡도가 O(n)인 것에 반해, O(2/n)까지 성능을 최적화할 수 있다.

 

하지만 시간복잡도를 더 줄일 수 있는 방법이 있다.

 

def mydivisor(number): # number : 12
    result = []
    for i in range(1, int(number**(1/2))+1):
        if number%i==0:
            result.append(i)
            if i < number//i:
                result.append(number//i)
		result.sort() 
        		# [1, 2, 3, 4, 6, 12]
    return result

 

이렇게 작성하면 시간복잡도를 O(n^1/2)까지 줄일 수 있다.