[Python] 프로그래머스 기사단원의 무기

[Python] 프로그래머스 기사단원의 무기

https://school.programmers.co.kr/learn/courses/30/lessons/136798

문제

코드

def solution(number, limit, power):
    my_list = []
    for i in range(1,number+1):
        temp = 0
        for j in range(1,int(i**0.5)+1):
            if i % j == 0:
                temp += 2
                if j == i**0.5:
                    temp -= 1
        if temp > limit:
            my_list.append(power)
        else:
            my_list.append(temp)
    return sum(my_list)

리뷰

약수를 구하는 일반적인 방법은 1부터 N까지 직접 나눠보면서 나머지가 0인 수를 찾는 방법이다.

이 방법은 O(N)의 시간 복잡도를 갖는다.

 

반면 이 문제는 N의 범위가 1 ~ 100,000 이므로 일반적인 방법을 사용하면 시간 초과가 발생한다.

자연수 N은 약수 두 개의 곱으로 나타낼 수 있다.

따라서 1부터 N의 제곱근까지 반복문을 돌리면서 약수를 찾으면 된다.

이 경우 시간 복잡도는 O(N^(1/2))이다.

 

다만 N이 제곱수인 경우 N = A * A와 같이 두 약수가 중복되므로 예외 처리를 하였다.