[Codewars] Integers: Recreation One

▶  문제 : 

▶  내 답안 : 

import math
def list_squared(m, n):
    result = []
    for i in range(m,n+1) :
        a = [ v for v in range(1, int(math.sqrt(i))+1) if i%v ==0 ]
        b = [ int(i/v) for v in range(1, int(math.sqrt(i))+1) if i%v ==0 ] 
        c = list(set(a + b))
        sq_sum = sum([math.pow(v,2) for v in c])
        if math.sqrt(sq_sum) % 1 == 0 :
            result.append([i,int(sq_sum)])
    return result

- N의 모든 약수를 탐색하는 시간(이중 for문의 시간 복잡도) : O(N)

- N의 제곱근까지의 약수를 구하고 그 짝이되는 약수를 구하는 시간 : O(N^(1/2))

 

▶  모범답안 : 

def list_squared(m, n):
    out = []
    for i in range(m,n+1):
        # Finding all divisors below the square root of i
        possibles = set([x for x in range (1,int(i**0.5)+1) if i%x == 0])
        # And adding their counterpart
        possibles.update([i/x for x in possibles])
        # Doubles in the possibles are solved due to the set
        val = sum(x**2 for x in possibles)
        # Checking for exact square
        if (int(val**0.5))**2 == val: out.append([i, val])
    return out

▶  배워야할 부분 :  set.update() 

>>> k = {1, 2, 3}
>>> k.update([3, 4, 5])
>>> k
{1, 2, 3, 4, 5}

 

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