[파이썬] 프로그래머스 기사단원의 무기 풀이

문제 확인

프로그래머스

나의 풀이

• 약수의 개수는 약수의 정의와 소인수 분해의 성질로 확인할 수 있다.
• 약수(소인수)를 찾기 위해서 1(2) ~ N까지 전부 확인할 경우, 시간 복잡도는 $O(N^2)$이 돼 시간 초과가 발생한다.
• 약수(소인수) 탐색은 $\sqrt N$ 만큼만 확인해도 되는 점을 활용하면, 시간 복잡도를 $O(N\sqrt N)$으로 줄일 수 있다.

from collections import defaultdict
# 성분의 곱을 계산할 수 있다.
from math import prod

# 약수 개수 구하기 1 : 소인수 분해 활용
def solution(number, limit, power):
    # 숫자 1 고려해서 초기 값 1로 설정
    answer = [1]
    for i in range(2, number + 1):
        # 소인수 분해 결과 저장 : 각 약수의 개수
        prime_cnt = defaultdict(int)
        for j in range(2, int(i ** 0.5) + 1):
            while i % j == 0:
                prime_cnt[j] += 1
                i //= j
        # 계산이 안 된 경우
        if i != 1:
            prime_cnt[i] += 1
        answer_temp = prod([k + 1 for k in prime_cnt.values()])
        answer.append(answer_temp)
    # 파워 제한
    answer = sum([i if i <= limit else power for i in answer])
    return answer

• i와 i // j가 동일한 경우를 제외하기 위해서 set 함수를 사용 했다.

# 약수 개수 구하기 2 : 약수의 정의 활용
def solution(number, limit, power):
    answer = 1
    # 약수 검사
    for i in range(2, number + 1):
        answer_temp = set()
        for j in range(1, int(i ** 0.5) + 1):
            # 약수라면
            if i % j ==0:
                answer_temp.add(j)
                answer_temp.add(i // j)
        # 파워 리밋 적용
        answer += len(answer_temp) if len(answer_temp) <= limit else power
    return answer

참고

에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유