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

프로그래머스 '약수의 개수와 덧셈' 문제 풀이입니다.

 

문제 링크

코딩테스트 연습 - 약수의 개수와 덧셈

● 문제 간단 설명

주어진 두 숫자 사이의 수에 대해서 약수의 개수가 홀수인 경우 그 값을 빼고, 짝수인 경우 값을 더하여 그 계산 값을 return 하는 문제

 

● 문제 해결 방향

약수를 다 찾아내는 방식이 가장 먼저 떠올라  반복문을 통해 각 수의 약수의 개수를 구하고,

그 개수의 홀 짝 여부를 판단하여 값을 계산해주었다.

 

● 문제 해결 코드

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

일단 무식하게 반복문을 다 때려 넣어서 만든 로직이다.

단순히 두 숫자 사이에 존재하는 수에 대해서 약수를 구하고, 그 갯수를 구해 적절한 연산을 해주는 로직이다.

 

이 방법은 아무리봐도 베스트 방법은 아닌 것 같아 조금 더 고민을 해보았다.

약수의 개수가 짝수인 경우는 각 약수들이 짝이 존재하는 경우이다.

12의 경우 1은 12, 2는 6, 3은 4처럼 모든 약수는 짝이 존재한다.

 

반면 약수의 개수가 홀수인 경우는 짝이 존재하지 않고, 본인을 제곱했을 때 해당 숫자가 되도록 하는 제곱근을 가질 때 홀수 개수의 약수를 가진다.

위 개념을 추가해보면

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

각 숫자에 대해서 **0.5나 .sqrt()를 사용해서 제곱근을 구하고 그 값을 1로 나누었을 때 0인 값은 정수 값을 약수로 가지는 제곱수이기 때문에 홀수개의 약수를 가질 것이다.

 

● 참고

Python 제곱과 루트 구하기