[Algorithm/Python] 파이썬 약수 구하기 (시간복잡도 줄여보기)

문제

1 이상의 자연수 N이 주어졌을 때, N의 약수 구하기

 

풀이

단순한 풀이 방법

def getMyDivisor(n):

    divisorsList = []

    for i in range(1, n + 1):
        if (n % i == 0) :
            divisorsList.append(i)

    return divisorsList
    
    

 

• for 문을 이용해 범위를 약수가 될 수 있는 최솟값인 1부터 최댓값인 자기 자신까지 돌려준다.
• 만약, 나머지가 0이라면 약수라는 뜻이므로 배열에 저장해준다.
• 이 방법을 사용할 경우 작은 수부터 i가 들어가므로 자동으로 오름차순 정렬이 된다.
• 시간 복잡도 : O(N)

더 효율적인 풀이 방법

def getMyDivisor(n):

    divisorsList = []

    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            divisorsList.append(i) 
            if ( (i**2) != n) : 
                divisorsList.append(n // i)

    divisorsList.sort()
    
    return divisorsList
    
    

 

• N = A * B 로 나타낼 수 있다는 것을 이용한 풀이이다. 항상 약수를 구하면 그 짝이 되는 수가 존재한다. (ex. 6 = 2 * 3 )
• for 문을 이용해 자연수 N의 제곱근까지의 약수를 구하면 그 짝이 되는 약수는 자동으로 구할 수 있다.
• N = A * B 일 때,  A == B 일 수 있기 때문에 (ex. 25 = 5 * 5 ) 값을 중복해서 넣어주지 않기 위해 if 문으로 제곱했을 때 n이 되지 않는지 검사를 해줬다.
  • 혹은 i != (n // i) 로 검사도 가능하다.
• 마지막에 오름차순으로 정렬을 해준 후 return 해주면 된다.
• 시간 복잡도 : O(N^(1/2))

관련 문제

2501번: 약수 구하기

 

---

 

다양한 방법으로 풀어보는것도 재밌는거같다 ㅎㅅㅎ

더 좋은 방법이 있다면 댓글로 알려주세요 !

@미닛메이드 Minnit