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

🔒 문제

• 약수의 합

문제 설명

 

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

제한 사항

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

입출력 예

n	return
12	28
5	6

입출력 예 설명

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

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

 

---

🔓 풀이

 

🔑 문제 해결 / 코드

def solution(n): 
    # 방법 1
    # 시간복잡도 4n + 3 = O(n)
    # answer = 0                # 대입연산 1
    # for i in range(1, n+1):   # 반복문 n + 2
        # if n % i == 0:        # 조건문 2n
            # answer += i       # 덧셈 연산 n
            
    # 방법 2
    # 시간복잡도 10√n + 5 = O(√n)
    answer = 0                              # 대입연산 1
    for i in range(1, int(n**(0.5)+1)):     # 반복문 √n +3
        quotient, remainder = divmod(n, i)  # 대입연산 3√n
        if remainder == 0:                  # 조건문 √n
            if quotient == i:               # 조건문 √n 
                answer += i                 # 덧셈 연산 √n
            else:                           # 조건문 √n
                answer += i + quotient      # 덧셈 연산 2√n
    return answer                           # 리턴 1

---

💉 피드백

방법 1은 n을 1부터 n까지의 모든 수로 나눠서 나머지가 0인 경우를 전부 더해서 답을 구해봤다.

 

빠르게 구현한 방법이지만 효율적이진 않다고 생각해서 2번 방법을 시도했다.

 

정수 n의 약수의 중간값은 n의 제곱근과 가까운 수 이므로 n을 1부터 n의 제곱근까지의 수로 나눠서 나머지가 0일 경우 나눈 수와 몫을 전부 더하는 방법으로 구현을 했다.

 

처음 실행을 했을 때 3가지 테스트를 실패했는데 약간의 서칭으로 제곱근이 약수인 수를 예외처리 하지 않았다는 걸 알게 되었다.

 

조건문을 하나 추가해서 나눈 수 와 몫이 같을 경우(제곱근이 약수인 경우)는 하나만 더하도록 수정을 했고 테스트를 통과했다. 

 

 

시간 복잡도

시간 복잡도를 계산해봤는데 맞게 계산했는지는 모르겠다.

answer += 1의 경우 덧셈 연산 1회가 아닌 대입 연산 1회 덧셈 연산 1회 총 2회가 실행된 건지,

range, divmod의 경우 1회의 연산과정이 맞는 건지,

조건문이 여러 개인 경우는 어떻게 계산하는 게 좋은지 등을 더 공부해야겠다.