[프로그래머스] 기사단원의 무기 - 제곱근 시간복잡도 적게 구하기

# 문제

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

프로그래머스

 

 

# 문제 요약

 

 

# 핵심 개념

 

숫자의 약수 개수 구하기

만약 36이라는 숫자의 약수를 구할 때 (1,2,3,4,6,9,12,18,36) 이렇게 되어있다

 

def cnt_prime(num):
    result = 0
    for i in range(1, num+1):
        if num % i == 0:
            result += 1
    return result

 

다음과 같은 형태로 약수의 개수를 구할 수 있으나 시간복잡도가 O(N)이 된다

 

36의 약수를 살펴보았을때 36에다가 루트를 씌우면 6이 된다

즉 1~6까지가 있고 그 이후에는 대칭으로 되어 있다

 

유의할 점은 6*6 = 36과 같은 제곱수일 경우 count += 1을 해주고

제곱수가 아닐 경우 count += 2를 해줄 수 있다

 

def cnt_prime(num):
    result = 0
    for i in range(1, int(num**0.5)+1):
        if num % i == 0:
            if i*i == num:
                result += 1
            else:
                result += 2
    return result

 

시간복잡도는 O(N^(1/2)) 가 된다

 

 

 

# 정답 코드

def cnt_prime(num):
    result = 0
    for i in range(1, int(num**0.5)+1):
        if num % i == 0:
            if i*i == num:
                result += 1
            else:
                result += 2
    return result

def solution(number, limit, power):
    lst = [i for i in range(1,number+1)]
    arr = []
    for i in lst:
        prime = cnt_prime(i)
        if prime > limit:
            prime = power
        arr.append(prime)
    return sum(arr)

 

# Reference

https://sohyeonnn.tistory.com/45

[프로그래머스] 기사단원의 무기 Python 풀이(제곱근 이용)