[코딩테스트] 약수 문제

김희정·2023년 2월 6일

약수 약수의 개수 약수의 개수와 덧셈

Coding Test

목록 보기

4/7

프로그래머스

문제 1. 순서 쌍의 개수

💡 문제 내용

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 1,000,000

입출력 예시 및 설명

n	result
20	6
100	9

입출력 예 1)

n이 20 이므로 곱이 20인 순서쌍은 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1) 이므로 6을 return합니다.

입출력 예 2)

n이 100 이므로 곱이 100인 순서쌍은 (1, 100), (2, 50), (4, 25), (5, 20), (10, 10), (20, 5), (25, 4), (50, 2), (100, 1) 이므로 9를 return합니다.

💡 문제 해석

이 문제는 입출력 예 1) 에서 보듯이 순서쌍이 튜플을 앞자리만 따서 변경하면 (1, 2, 4, 5, 10, 20)가 되고, 이는 가능한 약수의 개수를 묻는 것으로 해석할 수 있습니다.

🔍 약수란?

수론에서 약수(約數, 영어: divisor) 또는 인수(因數, 영어: factor, 전 용어: 승자(乘子))는 어떤 수를 나누어떨어지게 하는 수를 말한다.

위키 백과 - 약수

💡 문제 해결 코드

시간복잡도 O(N)의 경우에는 코드는 매우 단순합니다. 정말 단순히 모든 원소를 검사해, 원래 숫자와 원소를 나누었을 때, 나누어 떨어지는지 보면 됩니다.

아래는 Python 코드입니다.

# 약수를 구하는 함수
def get_divisor(n: int) -> list:
    return len([i for i in range(1, n+1) if n % i == 0])

# 약수의 개수를 반환
def solution(n):
    return get_divisor(n)

문제 2. 약수의 개수와 덧셈

💡 문제 내용

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

제한사항

1 ≤ left ≤ right ≤ 1,000

입출력 예시 및 설명

left	right	result
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 해야 합니다.

💡 문제 해결 코드

앞선 문제1과 문제2는 같은 내용의 문제지만, 해결해야될 문제의 수가 최대 999개까지 차이나기 때문에, 최대한 시간을 단축하기 위해 약수의 개수를 구하는 함수의 시간복잡도를 O(log N)으로 줄여보았습니다.

시간복잡도 O(log N)이란?

입력 데이터의 크기가 커질수록 처리 시간이 로그(log) 만큼 짧아지는 알고리즘

아래는 Python 결과 코드 입니다.

def get_divisor_count(n):
    digits = [len(set([i, n//i])) for i in range(1, int(n**0.5)+1) if n %i == 0]
    return sum(digits)

def transform(n: int):
    if get_divisor_count(n) % 2 == 1: n *= -1
    return n
    
def solution(left, right):
    arr = [transform(i) for i in range(left, right+1)]
    return sum(arr)