약수의 개수와 덧셈 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/77884

프로그래머스

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ left ≤ right ≤ 1,000

---

code

# Lv.1
# 약수의 개수와 덧셈
def solution(left, right):
    answer = 0
    for num in range(left, right + 1):
        temp = num ** 0.5
        if int(temp) == temp:
            answer -= num
        else:
            answer += num
    return answer

 

알고리즘

특정 수의 약수의 개수는 다음과 같은 특징을 지닌다. 만약 특정 수의 제곱근이 정수라면 특정 수의 약수의 개수는 홀수 개이며, 정수가 아니라면 약수의 개수는 짝수 개이다. 이유는 약수는 대체로 곱하면 특정 수가 될 수 있는 짝이 있다. 예시로 12의 약수인 1& 12, 2 & 6, 3 & 4가 있다. 그러나 25의 경우는 5 * 5로 짝이 같은 수이기 때문에 25의 약수는 1, 5, 25로 3(홀수)개다.

 

그래서 위의 코드처럼 특정 수의 제곱근이 정수인지 확인해 약수의 개수를 파악하고, 상황에 따라 특정 수를 더하거나 뺐다.

 

피드백

처음엔 아래 코드로 작성했었다. 반복문을 돌면서 특정 수의 약수의 개수를 하나씩 더해서 비효율적이다. 다른 사람의 코드에서 약수 개수의 특징을 알게 되어 위 코드로 수정했다.

# Lv.1
# 약수의 개수와 덧셈
def solution(left, right):
    int_list = [0] * (right - left + 1)
    # 약수의 개수 구하기
    for i in range(1, right + 1):
        for j in range(left, right + 1):
            if j >= i and j % i == 0:
                int_list[j - left] += 1
    # 결괏값 구하기
    answer = 0
    for i in range(left, right + 1):
        if int_list[i - left] % 2 == 0:
            answer += i
        else:
            answer -= i
    return answer

https://github.com/soaringwave/Python-algorithm-studying/commit/ca0f00f08e3863e391399412b62f3ab293ffb955

Add comments · soaringwave/Python-algorithm-studying@ca0f00f