문제링크
문제
Count the number of divisors of a positive integer n.
Random tests go up to n = 500000.
Examples
divisors(4) = 3 // 1, 2, 4
divisors(5) = 2 // 1, 5
divisors(12) = 6 // 1, 2, 3, 4, 6, 12
divisors(30) = 8 // 1, 2, 3, 5, 6, 10, 15, 30🚩문제해석
주어진 수의 약수의 개수를 구하시오.
divisor : 약수
문제 접근
- 첫번째 풀이
function getDivisorsCnt(n){
let cnt = 0;
for(let i = 1; i <= n; i++){
if(!(n % i)) cnt++;
}
return cnt;
}
아주 기본적인 접근이다. n까지의 자연수 중에서 소수의 개수를 구하는 것과 접근 자체는 같다. 그런데 문제가 있다. 이렇게 풀면 여기서는 모든 샘플테스트도 다 통과하였지만, 시간이 오래걸린다.
Time: 1734ms Passed: 603 Failed: 0위 코드의 실행 결과이다. 잘 생각해보면 카운트하는데 있어서 중복이 발생한다는 것을 알 수 있다. 예를 들어서 10의 약수를 구한다고 해보자.
[n] [i]
10 % 1 -> cnt = 1
10 % 2 -> cnt = 2
10 % 5 -> cnt = 3
10 % 10 -> cnt = 4
return cnt = 4위의 식을 살펴보면 알겠지만, i가 1과 2일 때 이미 10과 5는 약수로서 체크가 가능해진다. 즉 곱해서 10이 되는 수를 찾으면 자동으로 2개씩 체크가 가능해지는 부분이다. 이것이 어디까지 카운트하면 되는지를 생각하면, 제곱수가 n이 될 때까지 세면 된다. 위에서 보면 i가 3일 때 3 3 = 9이고 4 4 = 16으로 이미 제곱수가 n인 10을 넘어서기 때문에 그 전까지인 i가 3일때까지만 카운트 해주고 카운트해줄 때마다 cnt에 2를 더해주면 된다.(약수 1개를 찾은 것이 2개를 찾은 것과 같아지기때문이다.) 결과적으로 효율성이 대략 2배정도 올라갈 수 있다.
- 두번째 풀이
1 function getDivisorsCnt(n){
2 let cnt = 0;
3 for(let i = 1; i*i <= n; i++){
4 if(i*i == n) cnt++;
5 else if(!(n % i)) cnt += 2;
6 }
7 return cnt;
7 }위에서 설명한 것을 구현한 코드이다. 3번 라인에서 제곱수까지만 카운트되도록 한다. 4번라인의 if조건문의 의미는 만약에 제곱수인 n이 있다면 i * i == n일 때는 약수가 1개이기 때문에 이 부분을 따로 체크해주기 위한 코드이다.
Time: 1071ms Passed: 603 Failed: 0결과값이 약 700ms정도 빨라졌다.
결론
이번 문제는 수학적 관점에서 더 효율적인 세는 방법에 대해서 알아보았다. 사실 이 문제는 여기서 끝이 아니고 이 문제를 여러 방면으로 응용한 문제들이 많이 있다. 그러한 문제들도 모두 다 세는 방법도 있지만 약수와 배수의 수학적 관계를 잘 이용하면 조금 더 효율적으로 셀 수 있는 방법들을 찾을 수 있었다. 약수와 배수는 프로그램밍을 할 때, 여러 방면으로 이용되는 도구같은 느낌이다. 하지만 역시 수학인지라 쉽게 떠오르지 않는 안타까움(?)이 있다. 이러한 생각이 앞으로 내가 문제를 접근하기 전에 한번쯤 스쳐지나가는 생각이 되길 바란다. 😎
🚀 문제를 풀어나갈 때 생각의 흐름을 정리합니다. 또한 새로운 풀이에 대한 코드를 분석하고 모르는 부분에 대해서 정리합니다. 생각이 다른 부분에 대한 피드백은 언제나 환영합니다. 틀린 내용에 대한 피드백 또한 항상 감사합니다.
