프로그래머스 - 약수의 개수와 덧셈

문제 풀이

두 정수 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 해야 합니다.

 

나의 풀이

def how_many_measure(num):
    many = 0
    for i in range(1, num+1):
        if num % i == 0:
            many += 1

    return many

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

    return answer

설명

약수의 개수를 구하는 함수를 따로 만들어주고 나온 값이 짝수인지 홀수인지에 따라 더해주고 빼주었다.

 

개선 코드

여기서 개선하면 좋은 부분이 있었는데, 약수를 구하는 함수가 n개를 다 확인하지 않고도 짝수인지 홀수인지만 확인하면 되는 것이기 때문에 전체를 둘러볼 필요가 없다. 

 통과는 했지만 시간복잡도를 줄인다면, 주어진 num의 제곱근에 대해서만 비교를 해주면 된다.

예를 들어 제곱근이 정수이면 약수의 개수는 홀수가 될 것이다. 약수의 대칭성 성질 때문에, 그렇다면 시간복잡도가 기존에 내가 짠 코드보다 훨씬 줄어들 것으로 예상 된다. 

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