42. 기사단원의 무기 ★★ (약수의 개수)

유형 : 구현

풀이 시간 : 10분 -> 시간 초과

 

1. 단순 구현 

def solution(number, limit, power):
    answer = 약수(number, limit, power)
    return answer

def 약수(x, limit, power):
    ans = 0
    for i in range(1, x+1):
        tmp = 0
        for j in range(1, i+1):
            if i % j == 0:
                tmp += 1
        if tmp > limit:
            tmp = power
        ans += tmp
    return ans

 

시간 초과 발생.. 너무 단순한 알고리즘이다.

모두 for문으로 순회하니 시간 초과가 발생하였다. 

 

2. 최적화 방법

 1) for문을 돌리면서 limit가 temp 이상이 되는 경우 즉시 종료하도록 한다. 

def solution(number, limit, power):
    answer = 약수(number, limit, power)
    return answer

def 약수(x, limit, power):
    ans = 0
    for i in range(1, x+1):
        tmp = 0
        for j in range(1, i+1):
            if i % j == 0:
                tmp += 1
            if tmp > limit:
                tmp = power
                break
        ans += tmp
    return ans

 

  비교적 간단한 최적화 방법이었으나, 역시 시간 초과. 

 

 2) 1번 + 약수를 찾기 위해서 순회하는 범위를 제곱수까지로 한정

 - 1과 자기 자신도 약수에 포함되므로 2로 시작 

 - 2부터 순회하면서 나누기 => 제곱수까지만 순회

    * 만약 나누어진다면, 제곱수 (예) 4*4) 인 경우 tmp += 1 

      제곱수가 아닌 일반적인 경우 약수 2개를 찾은 것이므로 tmp += 2

 

def solution(number, limit, power):
    answer = 약수(number, limit, power)
    return answer

def 약수(x, limit, power):
    ans = 1
    for i in range(2, x+1):
        tmp = 2
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                if j == i ** 0.5: 
                    tmp += 1
                else:
                    tmp += 2
            if tmp > limit:
                tmp = power
                break
        ans += tmp
    return ans

 

- 순회 범위 줄이기, 중간에 break하기 모두 수행한 결과 

통과할 수 있었다.