[코딩테스트] 약수 문제

김희정·2023년 2월 6일
1

Coding Test

목록 보기
4/7

프로그래머스


문제 1. 순서 쌍의 개수

💡 문제 내용

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

제한사항

  • 1 ≤ n ≤ 1,000,000

입출력 예시 및 설명

nresult
206
1009
입출력 예 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. 약수의 개수와 덧셈

💡 문제 내용

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

💡 문제 해결 코드

앞선 문제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)

원소 탐색을 최대 log2 N 값 만큼 탐색하도록 range 함수에서 max 범위를 int(n**0.5)+1 으로 지정했습니다. 그 이유는 log2 N 값을 넘는 숫자는 이미 앞서 나온 숫자의 으로, 이미 카운팅 되었기 때문입니다.


마치며

오늘은 코딩테스트 입문 과정을 풀며 워밍업 시간을 가졌습니다!

profile
Java, Spring 기반 풀스택 개발자의 개발 블로그입니다.

0개의 댓글