기사단원의 무기 / 프로그래머스

 

첫 번째 시도

• 시간초과로 실패!

def solution(number, limit, power):
    ans = 0
    for i in range(1, number + 1):
        cnt = 0
        for j in range(1, i + 1):
            if cnt > limit:
                break
            if i % j == 0:
                cnt = cnt + 1
        
        if cnt > limit:
            ans = ans + power
        else:
            ans = ans + cnt
    return ans

 

탐색 범위를 제곱근까지만 구하기

• 약수는 짝이 맞춰서 있기 때문에 제곱근까지만 탐색해도 해당 값의 약수의 갯수를 모두 구할 수 있음
• 예시 : 20의 약수를 구하고 싶다
  • 1은 20의 약수 : 20 / 1 = 20 -> 20도 20의 약수
  • 2는 20의 약수 : 20 / 2 = 10 -> 10도 20의 약수
  • 4는 20의 약수 : 20 / 4 = 5 -> 5도 20의 약수
  • 20의 제곱근(4.xx)까지만 탐색해도 모든 약수 [1, 2, 4, 5, 10, 20]을 모두 구할 수 있음
• x가 N의 약수라면 N / x 도 N의 약수이다

 

정답

• 제곱수인 경우 중복되는 경우를 제외하기 위해서 if j != n // j: 조건 추가
  • 16의 약수를 구하는 경우 첫번째로 구한 약수는 4이고 그와 대응하는 약수를 구할 때 해당 대응 약수도 4이므로 중복 카운트 방지

def solution(number, limit, power):
    ans = 0
    for i in range(1, number + 1):
        cnt = 0
        for j in range(1, int(i ** 0.5) + 1):
            if cnt > limit:
                break
            if i % j == 0:
                cnt = cnt + 1
                if j != i // j:
                    cnt = cnt + 1
        
        if cnt > limit:
            ans = ans + power
        else:
            ans = ans + cnt
    return ans