11/9 기사단원의 무기

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

내 풀이(시간초과)

def solution(number, limit, power):
    number_power = [0] * (number + 1)
    for i in range(1, number + 1) :
        tmp_power = 0
        for j in range(1, i + 1) :
            if i % j == 0 :
                tmp_power += 1
                
        if tmp_power > limit :
            tmp_power = power
        number_power[i] = tmp_power
    
    answer = sum(number_power)
    return answer

제출 하면서도 뭔가 시간초과가 날거란 직감을 했지만 아니나 다를까 몇몇 케이스에서 시간초과가 났다. 약수를 구하는 과정에서 시간을 많이 잡아먹는 모양이다. 그래서 약수 검사 과정에서 범위를 루트를 이용해 줄여줬다.

고친 풀이

def solution(number, limit, power):
    number_power = [0] * (number + 1)
    for i in range(1, number + 1) :
        tmp_power = 0
        for j in range(1, int(i ** 0.5) + 1) :
            if i % j == 0 :
                tmp_power += 1
                if j ** 2 != i : # 약수가 제곱수가 아니라면 1을 한번 더 더해서 짝지어진 다른 약수를 카운트한다.
                    tmp_power += 1
        if tmp_power > limit :
            tmp_power = power
        number_power[i] = tmp_power
    
    answer = sum(number_power)
    return answer