[파이썬] 약수의 개수 구하기, 그런데 최적화를 곁들인

가장 기본적인 약수의 개수를 구하는 문제부터 시작해보자.

 

어떤 자연수 n이 주어졌을 때, n의 약수의 개수를 구하라.

약수는 나누어 떨어지게 하는 수를 의미한다.

n = int(input())
cnt = 0

for i in range(1, n+1):
    if n % i == 0:
        cnt += 1
        
print(cnt)

어떤 수를 입력 받고, 개수를 셀 변수를 선언한다.

range는 end에서 -1한 값까지 반복한다.

자기자신을 나누는 것도 가능하기에 n+1을 하여 구해준다.

 

시간복잡도는 n에 따라 반복횟수가 선형적으로 증가하기에 O(n) 이다. (1부터 n까지 반복)

 

이제 최적화를 해보자.

약수는 항상 a * b = n 쌍으로 존재하기 때문에 짝수 개가 된다.

ex) 6 = 1 * 6, 2 * 3 으로 총 2개의 쌍

그러나 제곱인 수, 제곱수는 약수의 개수가 홀수이다.

ex) 9 = 1 * 9, 3 *3 으로 한 쌍과 중복된 수(3)으로 3개가 나온다.

따라서 숫자가 제곱수인지 확인이 된다면, 약수의 개수가 짝수인지 홀수인지 판별이 가능하다.

n = int(input())

if int(n ** 0.5) ** 2 == n:
    print("제곱수 O")
else:
    print("제곱수 X)

 

사실 작은 숫자에서는 큰 차이가 발생하지 않겠지만,
https://school.programmers.co.kr/learn/courses/30/lessons/77884

프로그래머스

프로그래머스, 약수의 개수와 덧셈(77884) 문제에선 차이가 생길 수 있다.

주어진 숫자범위에서 약수의 개수를 구하고, 약수의 개수가 짝수라면 더하고, 홀수라면 빼는 문제이다.

흔히 알고 있는 방식으로 코드를 구성한다면 이렇게 나올 것이다.

def solution(left, right):
    result = 0
    
    for num in range(left, right+1):
        cnt = 0
           
        for i in range(1, num+1):
            if num % i == 0:
                cnt += 1
                
        if cnt % 2 == 0:
            result += num
        else:
            result -= num
            
    return result

반복문이 중첩되어 O(n^2)의 시간복잡도가 나온다.

최적화한 방식으로 코드를 재구성하면

def solution(left, right):
    result = 0

    for num in range(left, right + 1):
        if int(num ** 0.5) ** 2 == num:
            result -= num
        else:
            result += num

    return result

제곱수의 약수 개수는 홀수이기에, 제곱수라면 빼고, 아닐 경우 더하는 방식이다.

반복문을 하나줄여 시간복잡도가 O(n)으로 줄어들게 되었다.