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

문제

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

제한 조건

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

나의 풀이:

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

약수는 어떤 수를 나누어 나머지가 없이 떨어지게 하는 수를 말한다. 즉, n을 i로 나누었을 때 나머지가 0일 경우 i는 n의 약수가 되는 것이다. 이를 1 이상, n 이하인 수로 모두 확인해본 다음 약수인 값들을 더해주면 된다.

다른 사람들의 풀이 1.

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

문제 풀이 방식 자체는 크게 다르지 않지만 코드를 훨씬 더 단순하게 작성하는 방법이다.

배열을 생성해서 sum() 함수를 사용하면 더 쉽게 코드를 작성할 수 있겠다는 생각을 하기는 했는데, 내가 알고 있던 문법의 한계로는 오히려 코드가 길어져서 시도하지 않았다.

그런데 위의 풀이처럼 for문 안의 조건식에 if문을 이렇게 포함시킬 수 있는 줄 몰랐다. 또한 코드를 저렇게 [ ] 안에 작성해서 바로 배열을 만들 수 있다는것도 알게되었다.

다른 사람들의 풀이 2.

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

위 풀이 방식에서 한 발짝 더 나아간 풀이 방식이다.

정수 n의 약수를 구할 때 두번째로 가장 큰 약수의 값은 n/2 보다 클 수 없다. 예를 들어 36의 약수를 구할 경우 n인 36 다음으로 가장 큰 약수는 18이기 때문에 굳이 19, 20, 21… 등으로 36을 나눌 수 있는지 확인할 필요가 없다.

즉, n의 약수의 합을 구할 때 n/2 보다 작은 수들만 검사를 하면 되므로 성능을 약 2배 가량 향상시킬 수 있게된다.