[프로그래머스] Level1 : 기사단의 무기[Python]

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

프로그래머스

Level1치고 난이도가 있었던 문제. 문제의 의도에 맞는 알고리즘을 사용하지 않으면 시간초과가 난다.

(기존에 알고 있던 약수 개수 구하는 알고리즘을 사용하게 되면 시간복잡도가 O(n)이기 때문에)

# 일반적인 약수 개수 구하는 코드
N = 1000000000;

count = 0;
for i in range(1,N+1):
	if N % i == 0:
    	count += 1
print(count)

그렇다면 이 문제에서 요구하는 것은 약수 개수를 구할 때 효율적인 알고리즘을 생각해보라는 것.

 

방법

바로 n의 약수들 중 √n 이하인 것들만 구하면, 나머지는 n을 그것들로 나눠 구할 수 있다는 것이다.

예를 들어 √126은 11보다 크고 12보다 작다. 그리고 126의 약수들 중 11 이하인 것은 1, 2, 3, 6, 7, 9이다.

그러므로 나머지 약수들은 126을 1, 2, 3, 6, 7, 9로 나눈 126, 63, 42, 21, 18, 14이고, 더이상은 없다.

 

이 방법을 이해한 후 알고리즘을 작성하게 되면 시간복잡도는 무려 O(√n) 이 되므로 시간 복잡도가 굉장히 많이 줄어든다.

 

참고 사이트 : https://doodle-ns.tistory.com/32

아주 자세하게 설명이 되어 있으니 한 번 참고해보길 바람.

 

풀이 :

1. 위에 방법을 통해 그대로 구현하여 number만큼 반복문을 통해 1~number까지 각 수의 약수 개수를 구해줌

2. 구한 약수 개수를 limit과 비교하여 limit보다 클 경우 answer += power, 작거나 같을 경우 answer += 약수 개수 

 

코드 :

def solution(number, limit, power):
    answer = 0
    divisor_list = []
    for i in range(1,number+1):
        count = 0
        j = 1
        while j*j <= i:
            if j * j == i:      # 3 * 3 == 9와 같이 약수가 한개인 경우 
                count += 1
            elif i % j == 0:    # 8 % 4 == 2와 같이 약수가 두개인 경우
                count += 2
            j+=1
        divisor_list.append(count)
        if divisor_list[i-1] > limit:
            answer += power
        else:
            answer += divisor_list[i-1]
    
    return answer