[Python] 약수 개수 구하기 (시간복잡도 고려하기)

서론

프로그래머스 문제를 풀다가 약수의 개수를 구하는 과정에서 시간초과가 발생한 적이 있었다.

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

프로그래머스

약수의 개수를 구해야 하는 숫자가 크지 않다면 시간 제한 내에 문제를 해결할 수 있지만 그렇지 않은 경우 시간 초과에 걸릴 확률이 높아질 수 있다. 그래서 이번 글에서는 파이썬을 이용하여 약수의 개수를 구할 때 시간복잡도를 줄여 효율적으로 약수의 개수를 구하는 방법에 대해서 간단하게 알아보고자 한다.

단순 풀이

n = 100
count = 0

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

• 첫번째 방법은 1부터 n까지 모든 숫자를 돌면서 n으로 나누어 떨어지는지 확인하는 방법이다.
• 위 로직의 경우 시간복잡도는 O(N)을 가진다.

이번에는 시간복잡도를 고려한 로직을 살펴보자.

시간복잡도를 고려한 풀이

먼저, 로직을 이해하기 전에 약수가 가지고 있는 특징에 대해서 이해할 필요가 있다.

바로 자연수 N에 대해서 두 약수의 곱이 N이 되는 A와 B가 반드시 존재한다는 의미이다.

 

조금 더 쉽게 설명하면 자연수(N) = 약수(A) * 약수(B) 로 나타낼 수 있다는 것이다. 따라서 1부터 n까지 반복문을 돌지 않아도 되며, n의 제곱근까지 약수를 구하면 해당 약수들에 대한 짝이 되는 약수를 자동으로 구할 수 있다.

 

코드를 보며 이해해보자.

n = 100
count = 0

for i in range(1, int(n**0.5)+1):
    if i*i == n:
        count += 1
        continue

    if n % i == 0:
        count += 2 # 해당 약수의 짝에 대한 약수까지 카운트
    
print(count) # 9

 

i*i == n인 경우는 제곱 수인 경우이므로 이 때의 i는 짝이 존재하지 않기 때문에 +1을 해준다.

 

혹은 아래와 같이 코드를 구성할 수도 있다.

n = 100
count = 0

for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        count += 1
        if i ** 2 != n:
            count += 1

• 두번째 방법은 n의 제곱근까지 반복문을 돌며 그 때의 약수, 해당 약수에 대한 짝을 찾아 약수의 개수를 구하는 방법이다.
• 위 로직의 경우 시간복잡도는 O(N^(1/2))을 가진다.