[프로그래머스] lv.1 기사단원의 무기 python

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

프로그래머스

 

문제 설명

number까지 숫자들의 약수를 구하고,

만약 약수의 개수가 limit보다 크다면 power로 대치해서 result를 구하면된다.

 

제한 사항

1 ≤ number ≤ 100,000
2 ≤ limit ≤ 100
1 ≤ power ≤ limit

 

문제 풀이

number의 수가 10**5인것을 간과해선 안된다..

약수를 구하는데, 어떻게 구해야할까 엄청 고민했는데,

제한에 루트를 씌워 시간을 줄였다.

 

ex) 10 -> 1, 2, 5, 10을 약수로 갖는다, 1*10, 2*5 로 각각의 짝이 있으므로 제곱근보다 작은 수만큼 돌면서

반쪽을 찾고 cnt에 2씩 더해준다.

그리고 제곱수의 경우 if문을 넣어두어서 1개를 빼도록 했다. 4*4 같은 경우 똑같은 수의 곱하기 이지만 cnt는 2를 더했기 때문이다.

 

그렇게 구한 cnt가 limit보다 크다면 power로 대치한 후 

kg라는 새로운 list에 저장한다.

 

마지막에 kg의 합을 더하면 끝 !

 

def solution(number, limit, power):
    answer = 0
    kg=[]
    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
        kg.append(cnt)
#    print(kg)
    return sum(kg)