약수의 합 / 프로그래머스, 파이썬 코딩테스트 연습 연습문제

문제

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

 

 

제출답안

def solution(n):
    answer = sum([num for num in range(1, n+1) if not n % num])
    return answer

 

제출 후 개선답안

검사해야할 경우의 수 범위를 줄일 수 있다!
효율적인 약수 구하기 알고리즘 조사결과는 다음과 같다

1. 약수를 찾을 수 n의 제곱근 사이의 정수로 한정하여 약수를 찾는다
2. 나온 수로 n을 나눈 숫자들도 약수가 된다

정리하면, 1/2번 과정에서 구한 수들이 n의 약수

경우의 수가 n번에서 엄청나게 줄어들게 됨

다만, 1, 2번의 결과에 교집합이 발생하는 것으로 보임.
따라서, 1,2 번의 결과를 합집합 후 합하였음

def solution(n):
    under_sqrt = set([num for num in range(1, int(n**0.5)+1) if not n % num])
    rest = set([n//num for num in under_sqrt if not n % num])
    
    answer = sum(under_sqrt.union(rest))
    return answer

개선 전/후 코드 처리겨로가

문제 바로가기