Programmers - 약수의 개수와 덧셈 [Python3]

📃 문제 설명

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

📌 제한 사항

• 1 ≤ left ≤ right ≤ 1,000

📌 입출력 예

입출력 예 #1

• 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.
  
• 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

입출력 예 #2

• 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.
  
• 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

💡 How?

1. left부터 right 까지의 수 각각의 약수를 list에 담아 하나의 dictionary에 저장한다.
key: left부터 right 까지의 정수 중 한개 (n)
value: n의 약수를 담은 list

2. 약수를 구하는 방법
정수 a를 정수 b로 나누었을 때 나머지가 0이면, a는 b의 약수이다.

if b % a == 0:
	# a는 b의 약수이다

3. 약수의 개수가 홀수인 경우를 구분하는 방법 ⭐️
사실 이 문제는 간단하게 풀어냈지만, 이 포스트를 쓰게 된 이유는 3번과 관련이 있다..!
문제를 제출한 후, '다른 사람의 풀이'를 보는 과정에서
약수를 구하지 않고도 약수의 개수가 홀수인 수를 찾아내는 방법을 찾았다!
그건 바로, 제곱근의 정수 부분이 제곱근과 동일한 수를 찾는 것이다. 왜냐하면, 제곱수(4, 16, 36 등)의 약수 개수는 홀수이기 때문이다!! 🤭
제곱수가 아닌 수의 약수는 모두 쌍으로 이루어져 있어 짝수이지만, 제곱수의 약수는 (짝수 + 1)개, 즉 홀수이다.
16의 약수는 [1, 16, 2, 8, 4] 인데 4가 홀로 있어, 약수의 개수를 홀수로 만들어 준다.

이를 코드로 작성하면 아래와 같다.

if int(i**0.5)==i**0.5:
	# i의 약수의 개수가 홀수이다

여기서 i**0.5 는 제곱근을 구하는 방법이라고 한다 (처음 암 ㅎㅎ)

👉🏻 이처럼 기발한 아이디어를 활용하면, for 문 1개를 생략하여 속도가 향상된 코드를 작성할 수 있음을 알게 되었다!

👩🏻‍💻 구현 코드

import collections

def solution(left, right):
    answer = 0
    a = collections.defaultdict(list)

    for n in range(left, right +1):
        for i in range(1, n+1):
            if n % i == 0:
                a[n].append(i)
        # print(a)
        if len(a[n]) % 2 == 0:
            answer += n
        else :
            answer -= n

    return answer