Codility - CountFactors 문제풀이

나의 코드

시간 복잡도: O(sqrt(N)) or O(N)

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N):
    # write your code in Python 3.6
    
    if N == 1:
        return 1
    
    cnt = 0
    
    for i in range(int(N/2)):
        # 약수이면
        i = i+1
        if N/i%1 == 0:
            if N//i < i:
                break
            if N//i == i:
                cnt += 1
            else:
                cnt += 2
                
    return cnt        
    pass
    

 

누군가의 코드

시간복잡도: O(sqrt(N))

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N):
    # write your code in Python 3.6
    
    number_iter = 1
    factor_cnt = 0
    
    while number_iter*number_iter < N:
        # 약수이면
        if N/number_iter%1 == 0:
            factor_cnt += 2
            
        number_iter += 1
        
    if number_iter*number_iter == N:
        factor_cnt += 1
        
    return factor_cnt
    pass

 

 

약수의 경우 이렇게 풀면 꼭 O(N)의 성능이 나지 않고,

조금 더 빠른 추출이 가능하다. 참고!