프로그래머스 | 약수의 갯수와 덧셈 [파이썬 python]

프로그래머스

 

코드

def solution(left, right):
    answer = 0
    for i in range(left, right+1):
        c, j = 0, 1 # c = 약수의 개수, j = 약수
        
        # 약수의 개수를 구하는 과정
        while j <= i:
            if i % j == 0:
                c += 1
            j += 1
            
        if c % 2 == 0:
            answer += i
        else:
            answer -= i
    return answer

left, right 두 수가 주어지면 left부터 right까지의 모든 수들의 약수의 개수를 구해 해당 수가 짝수개의 약수를 가지면 더하고 홀수개의 약수를 가지면 빼는 문제이다.

문제를 보면 무엇을 구해야 하는지 헷갈릴 수 있다.

구하고자 하는 것은 약수의 개수들을 더하고 빼는 것이 아니라,
짝수개의 약수를 가지는 해당 수, 홀수개의 약수를 가지는 해당 수들을 더하고 빼는 것이다.

 

left = 13, right = 17이라면

1) 13부터 17까지의 수 13, 14, 15, 16, 17의 약수의 개수를 각각 구한다.

• 13의 약수의 개수: 2개 (1, 13) - 짝
• 14의 약수의 개수: 4개 (1, 2, 7, 14) - 짝
• 15의 약수의 개수: 4개 (1, 3, 5, 15) - 짝
• 16의 약수의 개수: 5개 (1, 2, 4, 8, 16) - 홀
• 17의 약수의 개수: 2개 (1, 17) - 짝

2) 약수가 짝수개이면 해당 수를 더하고, 홀수개이면 해당 수를 뺀다.

13 + 14 + 15 - 16 + 17 = 43

최종적으로, 43이 구하고자 하는 값이다.

 

위 과정을 코드로 나타내었다.

약수의 개수를 저장할 변수 c, 해당 값을 나눠 약수인지 판별할 변수 j를 먼저 선언하고 while문을 통해 약수의 개수를 구하는 과정을 반복한다.

모든 약수의 개수가 구해졌으면, 짝수인지 홀수인지 판별하여 answer에 더하고 뺀다.

 

다른 사람의 코드

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

코드를 제출하고 모든 케이스를 통과했음에도, 변수가 많이 선언된 것 같아서 다른 사람의 코드를 참고해 보았다.

이 코드에서 알 수 있었던 점은 if문의 조건이다.

왜 i의 제곱근을 구했을지 생각해 보니, 약수가 홀수개인 수는 제곱수라는 것을 알 수 있었다.

• 4 (1, 2, 4)
• 9 (1, 3, 9)
• 16 (1, 2, 4, 8, 16)
• 25 (1, 5, 25)

따라서, left에서 right까지의 수 중 해당 수가 제곱수이면 약수가 홀수개이므로 answer에서 해당 수를 빼주고, 아니면 answer에 해당 수를 더해주면 된다.