프로그래머스 합성수 찾기 JS ( Math.sqrt() - 제곱근을 범위로 이용 )

문제 설명

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

 

 

🙋‍♀️ 내 생각

약수의 개수를 기준으로 합성수를 판단하므로, 일단 길이가 n만큼인 배열을 만들고 그 값들을 돌면서 각각의 값의 약수의 개수를 구해야겠다고 생각했다.

그래서 n만큼의 길이를 가진 배열을 만든 다음, arr2를 또 만들어서 각 요소의 약수의 개수를 구하고 값이 3이상인것만 filter를 통해서 남긴다. 그런 다음 length를 통해서 몇 개인지 구한다.

 

 

✅ 내 코드

function solution(n) {
   let num =0
   let arr = Array.from({ length: n }, (_, i) => i + 1);
   let arr2=[]
   
   arr.forEach(v=> {
    let divisor = 1; 
    while(divisor<=v){
    if(v%divisor===0){
         num++
    }
        divisor++
   } 
       arr2.push(num)
       num=0
   })
    return arr2.filter(v=>v>=3).length
}

우선 각 요소의 약수의 개수를 셀 변수 num를 선언하고 0으로 초기화한다.

num은 약수가 추가될때마다 1씩 값이 증가하는 역할을 하면서 약수의 개수를 센다.

num은 일종의 계산기 역할을 한다고 보면 된다.

 

그리고 arr라는 변수에 Array.from을 통해서 길이는 n만큼이고 각 요소값은 인덱스+1을 한 배열을 생성한다.

(만약 n이 10이라면, arr=[1,2,3,4,5,6,7,8,9,10]으로 생성될 것이다)

 

그런 다음 arr2라는 빈배열을 만든다. arr2는 num이라는 각 요소의 약수를 순차적으로 담을 것이다.

(num을 담을 배열을 생성)

 

arr.forEach를 통해서 arr배열을 순회한다.

[1,2,3,4,5,6,7,8,9,10]의 값을 하나하나 조사할 것이다.

 

각 요소를 순회하면서 안에서는 while문을 통해서 조건을 만든다.

각 요소의 값을 나누어줄 변수를 divisor라고 선언한다. 1부터 나눠줄 것이므로 1로 초기화한다.

그런 다음 while문의 조건으로 divisor<=n 를 넣는다. 이렇게 하면 1부터 시작해서 n까지 약수를 검사할 수 있다.

(조건문을 통해서는 범위를 지정한다)

 

그리고 while문의 안에서는 if문을 통해서  v%divisor 가 0인 경우를 검사한다.

만약 나머지가 0이라면, 그 값은 약수가 되므로 num에 +1을 해야한다. 그래서 num++을 한다.

그러고나서, divisor의 다음 값을 넣어서 구해야하기 때문에 divisor에 ++을 통해서 +1을 한다.

 

이렇게 하나의 요소의 약수의 개수를 다 세면, while문을 빠져나온다.

이때의 num은 그 한개의 요소에 대한 약수의 개수일 것이다.

그래서 arr2에 그 값을 push하여 약수의 개수를 저장한다.

그리고 다시 다음 값의 약수의 개수를 구하여야 하기 때문에 계산기 역할을 하고 있는 num을 다시 0으로 초기화시킨다.

 

 

 

 

✔️ 개선할 점

반복문의 범위

약수의 개수를 세기위해서 모든 숫자를 다 확인할 필요가 없이, 숫자의 제곱근까지만 확인하면 된다.

약수는 숫자의 제곱근을 기준으로 대칭적으로 나타나기 때문이다.

 

예를 들어 12의 약수는 1, 2, 3, 4, 6, 12으로 대칭적으로 나타난다.

1과 12, 2와 6, 3과 4는 서로 짝을 이루는 것을 알 수 있다.

따라서 이러한 대칭적인 성질을 이용하면, 제곱근까지만 검사하여 시간복잡도가 훨씬 줄어든다.

 

 

 

 

 

💻  다른사람 코드중에 배울 것 

function solution(n) {
    let answer = 0;
    for(let i = 1; i <= n; i++) {
        const arr = [];
        for(let j = 1; j <= Math.sqrt(i); j++) {
            if(i % j === 0) {
                arr.push(j);
                if(i / j !== j) arr.push(i / j);
            }
        }
        if(arr.length > 2) answer++;
    }
    return answer;
}

제곱근을 이용해서 for문의 범위를 설정한 코드이다.

 

우선 answer이라는 변수를 만들고 0으로 초기화를 한다.

(약수의 개수가 3이상인 값을 저장할 용도)

 

그런 다음 첫번째 for문을 만든다. 이 for문의 범위는 1부터 n까지이다. 

(만약 n이 5라고 한다면 1,2,3,4,5의 값들을 다 검사해야하기때문에 범위가 n까지이다)

 

그리고 약수를 담을 배열 arr를 선언하고 빈배열로 초기화한다.

 

안쪽 for문은 n의 약수인지를 검사하는 역할을 한다.

이때 1부터 시작하여 제곱근까지만 검사한다. 위에서 설명을 적었던 바와같이 약수를 어차피 데칼코마니처럼 제곱근을 기준으로 짝을 이루고 있기 때문에 범위를 이렇게 지정한다. 

🔫 Math.sqrt(): 숫자의 제곱근을 반환

 

 

범위를 지정하고 나서 안에서는 if문을 통해서 약수인지를 검사한다. i%j ===0

만약 약수가 맞다면 arr배열에 push를 통해서 추가한다.

 

제곱근을 이용하여 범위를 지정할 경우, 주의할 점은 제곱근이 포함된 값이라면 제곱근이 약수로 두번 들어가지 않게 처리해야하는 것이다.

예를 들어 값이 16이라고 하면 제곱근은 4가 된다. 1,2,4,8,16과 같이 4를 기준으로 대칭이 만들어지지만 4가 두번 포함될 수 있기때문에 주의해야한다.

 

그래서 다시 if문을 통해서 제곱근이 아니라면이라는 조건을 넣는다.

if (i / j !== j) arr.push(i / j)

i/j !== j 는 제곱근이 아니라는 것을 의미한다.

( 반대로 생각해보면 더 이해하기가 쉬운데, i/j === j 로 생각해본다.

i/j = j를 다시 써보면 i = j**로 이해할 수 있다.  따라서 j는 제곱근이다0

 

(i / j !== j )와 같이 제곱근이 아닌 경우에만 i/j의 값을 배열에 push한다.

 

제곱근인 경우는 제외함으로써, 데칼코마니처럼 생긴 약수를 모든 숫자를 검사하지 않고 돌면서 또 제곱근인 경우에 생기는 약수를 두번세셀 경우도 배제한다.

 

위의 코드를 이해하기 위해서 n=16이라 가정하고 코드의 흐름을 일일이 쳐보면서 생각해보았다.

n=16일 경우, i의 범위는 1부터 16까지이다. 

따라서 i는 우선 1부터 시작한다.

 

1️⃣ 바깥쪽 for문에서 i=1을 먼저 돈다.

i=1

그리고 안쪽 for문에서의 j의 범위는 1부터 1까지이다.

j=1

i%j === 0 이므로 1을 arr에 push한다.

[1]

1/1 !== 1이 성립하지 않으므로 더 이상 push하지 않고 arr의 길이가 3이상인지를 검사한다.

3이상이 아니므로 아무것도 하지않고 바깥쪽 for문으로 가서 ++을 수행한다.

 

2️⃣ 바깥쪽 for문에서 i=2를 돈다.

i=2

안쪽 for문에서의 j의 범위는 1부터 1까지이다.

 j=1

2%1 === 0 이므로 1을 arr에 push한다.

[1]

2/1 !== 1 이 성립하므로 2/1의 값인 2를 arr에 push한다.   

[1,2]

arr의 길이가 3이상인지를 검사한다. 

3이상이 아니므로 아무것도 하지않고 바깥쪽 for문으로 가서 ++을 수행한다.

 

......

위와 같은 원리로 3,4,5....계속 반복한다.

 

1️⃣6️⃣ 바깥쪽 for문에서 i=16을 돈다.

i=16

안쪽 for문에서의 j의 범위는 1부터 4까지이다.

j=1

16%1 === 0 이므로 1을 arr에 push한다.

[1]

16/1 !===1 이 성립하므로 16/1의 값인 16을 arr에 push한다.

[1,16]

 

i=16, j=2

16%2 === 0 이므로 2를 arr에 push한다.

[1,16,2]

16/2 !===2 이 성립하므로 16/2의 값인 8을 arr에 push한다.

[1.16,2,8]

 

i=16, j=3

16%3 === 0이 아니므로 아무것도 push하지 않는다.

 

i=16, j=4

16%4 ===0 이므로 4를 arr에 push한다.

[1,16,2,8,4]

16/4 !== 4 가 성립하지 않으므로 push하지 않는다.

 

여기서 4는 16의 제곱근이므로 만일 i/j !===j와 같은 장치를 해두지 않고 바로 i/j를 push한다면 4가 2번 push되는 문제가 발생할 것이다.

그리고 length가 3이상이므로 answer에 ++을 한다.

 

 

 

 

🙋‍♀️ 내 생각

약수가 데칼코마니처럼 생기는 성질을 이용해서 제곱근을 범위값으로 지정하여 시간복잡도를 낮춰서 효율성을 높일 수 있다는 것을 학습하였다. 일일이 약수를 구하는 방법만 생각했었는데 이런식으로도 더 효율적으로 코드를 짤 수 있구나 깨달았다.

다만 제곱근이 2번 겹쳐서 추가될 수 있는 점을 명심하고 주의해서 코드를 짜야할 것 같다.