Count the divisors of a number <7 kyu>

jjanmo·2020년 1월 14일
0

Codewars에서 뒹굴기

목록 보기
18/32

문제링크

문제

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정도 빨라졌다.

결론

이번 문제는 수학적 관점에서 더 효율적인 세는 방법에 대해서 알아보았다. 사실 이 문제는 여기서 끝이 아니고 이 문제를 여러 방면으로 응용한 문제들이 많이 있다. 그러한 문제들도 모두 다 세는 방법도 있지만 약수와 배수의 수학적 관계를 잘 이용하면 조금 더 효율적으로 셀 수 있는 방법들을 찾을 수 있었다. 약수와 배수는 프로그램밍을 할 때, 여러 방면으로 이용되는 도구같은 느낌이다. 하지만 역시 수학인지라 쉽게 떠오르지 않는 안타까움(?)이 있다. 이러한 생각이 앞으로 내가 문제를 접근하기 전에 한번쯤 스쳐지나가는 생각이 되길 바란다. 😎

🚀 문제를 풀어나갈 때 생각의 흐름을 정리합니다. 또한 새로운 풀이에 대한 코드를 분석하고 모르는 부분에 대해서 정리합니다. 생각이 다른 부분에 대한 피드백은 언제나 환영합니다. 틀린 내용에 대한 피드백 또한 항상 감사합니다.

profile
눈길을 걸어갈 때 어지럽게 걷지 말기를.

0개의 댓글