[Python 프로그래머스] 약수의 개수와 덧셈

[문제]

[Python 프로그래머스] 약수의 개수와 덧셈

[해결]

def solution(left, right):
    answer = 0
    for i in range(left,right+1):
        count = 0
        for n in range(1,i+1):
            if i % n == 0:
                count +=1
        if count % 2 ==0:
            answer += i
        else:
            answer -= i
    return answer

[정리 및 새롭게 알게 된 점]

1. 첫번째 loop에서는 left부터 right까지의 수를 추출하였고 두번째 loop에서는 각각의 추출된 i에 대해 해당 약수의 개수를 구하는 for loop를 돌려 약수의 개수를 count 변수에 입력하였다.

2. 구한 약수의 개수를 바탕으로 약수의 개수가 짝수이면 answer에 더하였고, 그렇지 않으면 answer값에서 빼주었다.

 

나의 경우 이중 for loop을 이용해 결괏값을 계산하였지만 이 경우 알고리즘 측면에서 시간복잡도가 증가하는 단점이 있다. 다른 해결법을 찾아본 결과 '제곱수의 약수는 항상 홀수이고, 제곱수가 아닌 수의 약수는 짝수개가 된다는 사실'을 발견하였고 이러한 사실을 이용하여 코드를 수정하면 아래와 같은 코드로 문제를 해결할 수 있다.

 

def solution(left, right):
    answer = 0
    for i in range(left,right+1):
        if int(i**0.5)**2 == i:
            answer -=i
        else:
            answer +=i
    return answer