[Python] 약수의 개수와 덧셈 (프로그래머스 Lv.1)

문제 설명

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

---

제한사항

• 1 ≤ left ≤ right ≤ 1,000

---

 

입출력 예leftrightresult

13	17	43
24	27	52

---

입출력 예 설명

입출력 예 #1

• 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

수약수약수의 개수

13	1, 13	2
14	1, 2, 7, 14	4
15	1, 3, 5, 15	4
16	1, 2, 4, 8, 16	5
17	1, 17	2

• 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

입출력 예 #2

• 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

수약수약수의 개수

24	1, 2, 3, 4, 6, 8, 12, 24	8
25	1, 5, 25	3
26	1, 2, 13, 26	4
27	1, 3, 9, 27	4

• 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

 

문제 이해

- left에서 right까지의 수 중에서 약수의 갯수가 짝수인 수는 더함.

- 약수의 개수가 홀수인 수는 빼야함. 그리고 그 총합을 리턴.

 

문제 풀이

- 어떤 수의 약수를 구하는 알고리즘을 알고 있으면 쉽게 해결 할 수 있는 문제인 것 같다. 모른다면 1~10까지의 수로 각 수를 다 나눠보면 되는데, 이 경우 입력 갯수 n에 비례하기 때문에 입력이 커지면 실행시간도 비례해서 증가한다. ( O(n))

- 약수의 개수를 구하려면 먼저 어떤 수의 제곱근을 생각해야 한다. 어떤 수 n의 약수를 나열했을 때 n의 제곱근은 약수 중 가운데에 위치하게 된다. 루트 n이 정수가 아닌 경우와 정수인 경우가 있는데, 정수일 때는 바로 16, 36 처럼 같은 수가 제곱 된 수이다.

- 어떤 수에 대해서 1부터 (루트n)+ 1 까지 반복하면서 나누어 떨어지는지 점검한다. 만약 떨어진다면, 그 수는 n의 약수인데, 이때 루프가 n의 제곱근까지만 진행되므로 n의 제곱근 이후의 수를 고려해서 n에서 나누어떨어지는 약수를 나눠주면 제곱근 이후의 약수들이 나온다. 그리고 그 수들을 새로운 배열에 담아준다.

- 마지막으로 16, 36 처럼 같은 수가 곱해지는 수는 약수 중 제곱근이 중복해서 배열에 담아지므로, 집합으로 만들거나 중복을 제거해줘야 한다.

 

코드

def solution(left, right):
    count = 0
    for i in range(left, right+1):
        arr = []
        l = 0
        for j in range(1,int(i**0.5)+1):
            if i%j == 0:
                arr.append(j)
                arr.append(i//j)
        l = len(set(arr))
        if l%2==0:
            count += i
        else:
            count -= i
    return count