[프로그래머스] Lv1 - 기사단원의 무기

문제

프로그래머스 연습문제

• Lv 1. 기사단원의 무기 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/136798

코드 구현

def get_yaksu_count(num):
    count = 0

    # for i in range(1, num+1):
    #     if(num % i == 0):
    #         count += 1
    
    for i in range(1, int(num**(1/2))+1):
        if(num % i == 0):
            count += 1
            if ((i**2) != num) :
                count += 1
    
    return count

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

    answer = sum(yak_su)
    
    return answer

풀이

• 1부터 number까지의 각 약수 개수를 구한 뒤 → limit보다 큰 개수를 가진 값은 → power로 변경하면 되는 간단한 알고리즘이다.
• 그러나 시간복잡도에서 1부터 number까지의 약수의 개수를 구하는 부분이 $O(n)$ 만큼 걸리는데 여기서 number의 최대로 들어갈 수 있는 값이 100,000이므로 절반의 테스트케이스에서 런타임에러가 발생하였다.
• 이를 위해 약수를 구하는 for문을 변경해줄 필요가 있었다.
  • 약수는 사실상 각자 짝을 가지고 있다.
    → 따라서 제곱수를 기준으로 for문을 절반까지만 돌린다면 시간복잡도를 $O(n^{1/2})$까지 줄여줄 수 있다!
  • 자기자신인 n을 1부터 n의 제곱근까지 하나씩 나눠본다 → 만약 i가 자기자신과 나누어 떨어진다면 → i의 제곱한 값을 확인 → 만약 i가 n의 제곱근이 아니면 → n // i 값 또한 약수

What I learned

▶️ 효율적인 약수 구하는 알고리즘 (시간복잡도 $O(n^{1/2})$)
참고 : https://minnit-develop.tistory.com/16

def getMyDivisor(n):

    divisorsList = []

    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            divisorsList.append(i) 
            if ( (i**2) != n) : 
                divisorsList.append(n // i)

    divisorsList.sort()
    
    return divisorsList