문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/136798
문제를 해결하는 순서는 다음과 같다.
- 개별 숫자의 약수의 개수를 연산하는 함수를 만든다.
- 개별 숫자의 약수의 개수가 limit를 넘으면 power 넘지 못하면 약수의 개수를 result에 더해 준다.
- 1부터 number까지 모든 숫자에 대해 2번 과정을 반복한다.
이때 가장 중요한 것은 1번 과정을 효율적으로 구사하는 것이다. 약수의 개수를 구하기 위해 1부터 number까지 모든 숫자로 나눠 본다면 당연히 시간복잡도는 O(n)이 나온다. 그러면 solution 함수에서 해당 함수를 n번 사용하므로 solution 함수의 시간복잡도는 O(n^2)로 매우 비효율적인 알고리즘이 된다.
하지만 이 문제를 멋지게 해결할 방법이 있다! 그것은 약수의 특징에서 알 수 있다. 약수는 자신을 나누었을 때 나누어 떨어지는 어떤 수를 의미한다. 그런데 나누어 떨어졌다는 것은 곧 몫으로 나누어도 나누어 떨어진다는 것을 의미한다. 힌트는 여기에 있다.
100을 나눌 때, 2로 나누어도 떨어지고 몫인 50으로 나누어도 떨어진다. 그러면 이러한 수들을 짝이라고 생각하고 묶어보자. [1, 100], [2, 50], [4, 25], [5, 20], [10, 10] 이렇게 5쌍이 나온다. 그런데 10은 서로 겹치므로 1을 빼주어야 한다. 이렇게 했을 때, 우리는 멋진 방법이 보이게 된다. 사실 전부 짝지어져 있기 때문에 우리는 100까지 셀 필요없이 10까지만 세면 약수의 개수를 알 수 있다. 1,2,4,5,10을 2번씩 세주고 제곱근이 있는 숫자만 1을 빼주면 될 것 같다.
실제로 이렇게 계산을 하게되면 logn번만 계산하면 되므로 solution은 시간복잡도는 O(nlogn)으로 줄어들게 된다.
def solution(number, limit, power):
result = 0
for i in range(1, number+1):
weight = get_divisor(i)
if weight > limit:
result += power
else:
result += weight
return result
def get_divisor(num):
cnt = 0
if num ** 0.5 == int(num ** 0.5):
cnt -= 1
for i in range(1, int(num ** 0.5)+1):
if num % i == 0:
cnt += 2
return cnt파이썬 코딩을 할 때, 한가지 팁을 주자면 함수를 여러 번 사용하지 않는 것이 좋다. weight를 2번 사용하는데 get_divisor()로 치환하면 라인 수가 줄어들지만 시간적으로 손해를 보게 된다. 그 이유는 java, c++과 같은 컴파일 언어는 컴파일 과정 중 최적화가 이루어져 가까운 라인에 같은 내용의 함수가 여러 번 사용되면 재사용 되지만 python의 경우 인터프리트 언어이기 때문에 같은 라인이 아니라면 그냥 2번 실행한다.
