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

풀이

• 해당 문제는 약수를 찾기위한 범위를 어떻게 지정하냐에 따른
• 시간 초과를 해결하는 문제로
• 단순히 1부터 해당 숫자까지 또는 해당 숫자의 절반까지를 조사하게 되면
• 시간 초과가 발생하여 해결하지 못하게 된다.
• 그래서 지난 소수 찾는 문제에서 확인한 것 처럼
• 해당 숫자의 루트를 씌운 값까지 찾게 한다면 반복 횟수를 줄이며 탐색할 수 있기에
• int(i**(1//2)+1로 작성하여 해결
• 그리고 set 타입 s에 추가하도록하여 중복된 것은 없애도록 하여 조건 분기에 따른 처리 후 해결

 

def solution(number, limit, power):

    result = [0]*number

    result[0] = 1

    s = set()

    for i in range(2,number+1):

        for j in range(1,int(i**(1/2))+1):

            if not i%j:

                s.add(j)

                s.add(i//j)

        result[i-1] = power if len(s) > limit else len(s)

        s.clear()

    return result