[Python3] 프로그래머스 기사단원의 무기 (약수 구하기, 제곱근)

실패.

def solution(number, limit, power):
    answer = 0
    tmp = [(i+1) for i in range(number)]
    tmp2 = []
    for i in tmp:
        cnt = 0
        for j in range(1, i + 1):
            if (i % j == 0) :
                cnt+=1
        tmp2.append(cnt)
    # print(tmp2)
    
    for i in range(len(tmp2)):
        if tmp2[i] > limit:
            tmp2[i] = power
    # print(tmp2)

    
    # for i in tmp2:
    #     if i > limit:
    #         answer += power
    #     else:
    #         answer += i
    
    return sum(tmp2)

성공.

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

풀이.

• 먼저 제곱근까지 구하는것이 Key 이다.
  • 해당 숫작까지 모두 약수 체크를 하면 타임아웃이 발생
  • j(i의 제곱근 까지)가 i의 약수인지 파악하고 약수라면 +2를 해주는것
  • 그리고 만약 j의 제곱이 i라면 1만 더해줘야하기 때문에 -1을 해줌
    • ex.) 16의 약수, 4인 경우
  • 약수의 갯수를 모두 더해서 limit보다 클 경우 power를 담우줘서 계산