프로그래머스 - 약수의 합

문제 설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한 사항

• n은 0 이상 3000이하인 정수입니다.

입출력 예

nreturn

12	28
5	6

입출력 예 설명

입출력 예 #1
12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.

입출력 예 #2
5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.

 

나의 풀이

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

 

개선 풀이

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

 

어려운 문제는 아니지만 여기서 약간 짚고 넘어가고 싶은 것이 있었다.

for 문 안에 범위를 n -> int(n/2)+1 로 줄여주었다.

왜냐면 본인을 제외한 가장 큰 약수는 2로 나눈 수 이기 때문! 물론 딱 안나누어 떨어질 수도 있기에 +1을 해주었다. 

따라서 약수 중 가장 큰(2로 나눈)값까지만 확인하고 마지막에 자신만 더해주면 문제를 풀 수 있다. 

 

시간 복잡도도 n -> n/2 로 줄일 수 있기 때문에 그리고 푸는 사람의 디테일이 이런데서 볼 수 있다. 쉬운 문제일지라도 개선할 부분을 항상 고민하는 개발자가 되자! 그러기 위해선 디테일... 이 중요하다!!!