[프로그래머스] 기사단원의 무기 - 파이썬

Programmers

기사단원의 무기

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

프로그래머스

문제

코드

• 시간 초과 코드
• 약수의 개수를 구할 때 단순하게 접근하면 시간 초과가 발생함.

def solution(number, limit, power):
    answer = 0
    lst = []
    for i in range(1, number+1):
        count = 0
        for j in range(1, i+1):
            if i % j == 0:
                count += 1
        lst.append(count)

    for k in lst:
        if k > limit:
            answer += power
        else:
            answer += k
    return answer

• 시간 초과를 해결하기 위해서는 약수를 찾을 때 해당하는 수의 제곱근까지만 찾으면 되는 개념을 활용해야함.
• 예를 들어, 36의 약수는 [1,2,3,4,9,12,18,36] 으로 구성되어 있음. 1-36, 2-18, 3-12, 4-9가 쌍을 이룰 수 있는 것을 알 수 있음.

 

• 수정된 코드

def solution(number, limit, power):
    answer = 0
    lst = []

    for n in range(1, number+1):
        count = 0
        for i in range(1, int(n**0.5) + 1):
            if n % i == 0:
                if i == (n // i):
                    count += 1
                else:
                    count += 2
        lst.append(count)

    for k in lst:
        if k > limit:
            answer += power
        else:
            answer += k
    return answer

 

• 만약 제곱근 값 * 제곱근 값으로 해당 수가 만들어진다면 약수를 count할 때 +1만하고 그 외의 경우에는 쌍을 이루기 때문에 count +2를 해주면 됨.