약수의 개수와 덧셈

출처: 프로그래머스

주소: https://programmers.co.kr/learn/courses/30/lessons/77884

코딩테스트 연습 - 약수의 개수와 덧셈

 

[문제 설명]

두 정수 left와 right 사이의 모든 수중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하는 것이다.

 

[예시]

입출력 예

[알고리즘]

 

1. 약수를 구하는 함수 작성

 - 기본적인 약수의 개수를 구하는 방법

  => 1부터 n-1까지 반복하여 약수인지를 확인하여 약수이면 개수를 늘리는 방법

  => 이렇게 구하면 O(n)의 시간 복잡도를 가진다.

 

 - 반복횟수를 줄여서 약수의 개수를 구하는 방법

   => 1부터 √n 반복해서 약수를 구하면 O(√n)의 시간 복잡도를 가진다.

      ex) n=9이면, 1, 3, 9이므로 1 2 3까지만 확인하면 되기 때문에 1 ~ √n까지만 반복한다.

def num(n):
    # 약수의 개수 저장
    res = 0
    # 1 ~ n^(1/2) 반복
    for i in range(1, int(n**(1/2)) + 1):
        # 약수이면 1 더하기
        if n % i == 0:
            res += 1
            # 제곱수가 아닌 경우 1번 더 더하기
            # ex) 3^2 = 9에서 3과 같은 경우를 제곱수
            if i * i != n:
                res += 1
                
    return res

def solution(left, right):
    # 결과
    answer = 0
    
    # left ~ right 반복
    for val in range(left, right+1):
        # 약수의 개수가 짝수
        # 더하기
        if num(val) % 2 == 0:
            answer += val
        # 약수의 개수가 홀수
        # 빼기
        else:
            answer -= val
    return answer

3. 결과 출력

 

 

[느낀 점]

 - 약수를 구하는 과정에서 굳이 n번 반복할 필요가 없다.

 - 항상 효율성을 생각해보자