Python/약수의 합

 

링크

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

프로그래머스

 

문제

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

정답

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

 

def getMyDivisor(n):

    divisorsList = []

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

    divisorsList.sort()
    
    return divisorsList

해설

• for 문을 이용해 범위를 약수가 될 수 있는 최솟값인 1부터 최댓값인 자기 자신까지 돌려준다.
• 만약, 나머지가 0이라면 약수라는 뜻이므로 배열에 저장해준다.
• 이 방법을 사용할 경우 작은 수부터 i가 들어가므로 자동으로 오름차순 정렬이 된다.
• 시간 복잡도 : O(N)

• N = A * B 로 나타낼 수 있다는 것을 이용한 풀이이다. 항상 약수를 구하면 그 짝이 되는 수가 존재한다. (ex. 6 = 2 * 3 )
• for 문을 이용해 자연수 N의 제곱근까지의 약수를 구하면 그 짝이 되는 약수는 자동으로 구할 수 있다.
• N = A * B 일 때,  A == B 일 수 있기 때문에 (ex. 25 = 5 * 5 ) 값을 중복해서 넣어주지 않기 위해 if 문으로 제곱했을 때 n이 되지 않는지 검사를 해줬다.
  • 혹은 i != (n // i) 로 검사도 가능하다.
• 마지막에 오름차순으로 정렬을 해준 후 return 해주면 된다.
• 시간 복잡도 : O(N^(1/2))

새롭게 이해한 내용

• 약수를 구하는 방법과 효율을 갖기 위해 더 고민할 수 있는 방식이 있음을 알았다