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

 

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

프로그래머스

 

 

 

 

 

✅ 1부터 n까지의 정수를 n에서 나누었을 때 나머지가 0인 값들을 모두 더함

 

그런데 굳이 1부터 n까지의 정수를 모두 나누어 볼 필요가 없다는 생각을 했다. 

1부터 n까지 정수를 확인하지 않고, n//2까지만 확인을 해도 되는 것이다. 

 

8 : 1, 2, 4, 8

9:  1, 3, 9

10 :  1, 2, 5,10

25: 1, 5, 25

 

 

위의 예시를 보면 정수는 자기 자신 즉, n을 제외하고 가장 큰 약수가 n//2를 넘는 경우가 없기 때문이다.

 

✅ 1부터 (n//2) 까지의 정수를 n에서 나누었을 때 나머지가 0인 값들을 모두 더함

 

나의 코드

def solution(n):
    answer = n
    
    m=n//2
    
    while m>0:
        if n%m==0:
            answer+=m
        m-=1
    
    
    return answer

 

⏱️ 시간 복잡도 : O(n)

 

---

다른 사람 코드

 

물론 내가 작성한 코드와 시간복잡도가 동일하지만 코드가 매우 간결하고 깔끔하기에 첨부한다 !

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