규도자 개발 블로그

[프로그래머스/Level1/파이썬3(python3)] 약수의 개수와 덧셈 본문

알고리즘/풀이

[프로그래머스/Level1/파이썬3(python3)] 약수의 개수와 덧셈

규도자 (gyudoza) 2021. 7. 12. 20:18
반응형

[프로그래머스/Level1/파이썬3(python3)] 약수의 개수와 덧셈

문제

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

제한사항

  • 1 ≤ leftright ≤ 1,000

입출력 예

leftrightresult
131743
242752

입출력 예에 대한 설명

  • 입출력 예 #1

    • 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.
    약수약수의 개수
    131, 132
    141, 2, 7, 144
    151, 3, 5, 154
    161, 2, 4, 8, 165
    171, 172
    • 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.
  • 입출력 예 #2

    • 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.
    약수약수의 개수
    241, 2, 3, 4, 6, 8, 12, 248
    251, 5, 253
    261, 2, 13, 264
    271, 3, 9, 274
    • 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

풀이

def solution(left, right):
    answer = 0
    for i in range(left, right+1):
        divisors_list = []
        for j in range(1, i+1):
            if i % j == 0:
                divisors_list.append(j)
        if len(divisors_list) % 2 == 0:
            answer += i
        else:
            answer -= i
    return answer

설명

나는 그냥 설명에서 나온 그대로 코딩했는데 다른 사람의 풀이를 보니 제곱수(1, 4, 9, 16...)의 성질을 이용한 사람들이 많았다. "제곱수의 약수의 개수는 홀수이고 제곱수가 아닌 경우는 짝수"라는 성질이 있는데 이걸 이용해 약수의 개수를 구하는 단계에서 해당 수가 제곱수인지 아닌지 검사하는 로직을 통해 더하거나 빼는 방식이 있다.

 

반응형
0 Comments
댓글쓰기 폼