합성수 찾기
2024. 8. 6. 18:00ㆍ코딩테스트 입문
https://school.programmers.co.kr/learn/courses/30/lessons/120846
문제 설명
약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ n ≤ 100
입출력 예
n | result |
10 | 5 |
15 | 8 |
입출력 예 설명
입출력 예 #1
- 10 이하 합성수는 4, 6, 8, 9, 10 로 5개입니다. 따라서 5를 return합니다.
입출력 예 #1
- 15 이하 합성수는 4, 6, 8, 9, 10, 12, 14, 15 로 8개입니다. 따라서 8을 return합니다.
합성수의 개수를 찾아내는 문제입니다.
합성수를 찾기 위해서는 약수의 개수를 찾아야 하므로, 약수 개수를 찾는 함수를 따로 만들면 편하게 풀 수 있습니다.
다만 이 약수를 찾는 게 정말 효율적인지는 조금 고민해봐야겠네요.
파이썬으로 문제를 풀어보겠습니다.
def cnts(n):
# 약수의 개수 cnt
cnt = 0
# 제곱근까지만 반복
for i in range(1, int(n ** (1/2)) + 1):
# 좌우 대칭 관계이므로 2씩 추가
if n % i == 0:
cnt += 2
# 제곱 관계일 경우 1개 삭제
if i**2 == n:
cnt -= 1
return cnt
def solution(n):
# 약수의 개수가 3개 이상인 값들의 배열로 저장
# 해당 배열의 길이 = answer
answer = len([i for i in range(n + 1) if cnts(i) >= 3])
return answer
이 코드는 엄청 효율적이진 않습니다. 시간 복잡도는 O(n√n) 입니다.
에라토스테네스의 체를 조금 응용해서 문제를 더 빠르게 풀 수 있습니다.
def solution(n):
# n까지 숫자의 약수 개수를 추가합니다.
divisor_count = [0] * (n + 1)
# 각 숫자마다 배수들에 약수 개수를 추가합니다.
for i in range(1, n + 1):
for j in range(i, n + 1, i):
divisor_count[j] += 1
# 3개가 넘는 약수를 가진 숫자들의 개수를 합칩니다.
answer = sum(1 for i in range(n + 1) if divisor_count[i] >= 3)
return answer
원래라면 소수가 아닌 값들을 삭제하는 용도지만, 반대로 개수를 미리 증가시키는 데 사용했습니다.
이 코드는 미리 배열에 저장해두기 때문에 좀 더 빠르게 구할 수 있습니다.
이론상 O(nlogn)의 시간 복잡도를 갖습니다.