ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [프로그래머스 Level 1] 소수찾기
    알고리즘 문제풀이 2020. 1. 7. 20:37

     

     


    1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

    소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
    (1은 소수가 아닙니다.)

    제한 조건

    • n은 2이상 1000000이하의 자연수입니다.

    입출력 예

    n                      result

    10 4
    5 3

     


    위 문제를 처음 접했을 땐 평범한 소수찾기 문제인 거 같아서 매우 쉽다고 생각을 했다.

    근데 범위 내에서 소수를 구하는 문제이기 때문에 에라토스테네스의 체를 활용하는 게 좋겠다는 생각이 들었다.

    그럼 한 번 구현해보자.

    function solution(n){
        var answer = Array(n+1).fill(1); // ㉠
        answer[1] = 0;
        answer[0] = 0;
        for(var j = 2; j <= Math.sqrt(n); j++){ // ㉡
            for(var k = j; j * k <= n; k++){ // ㉢
                answer[j * k] = 0;
            }
        }
        var count = 0;
        for(var num in answer) if(answer[num]) count++;
        return count;
    }

    위의 식에서 ㉠으로 인해 계속 효율성 문제가 발생했었다.

    이전 식에선 answer이라는 배열에 n이 10이면 [0,,,,10] 이런 식으로 각 인덱스에 해당하는 값을 할당해주었다.

    이러니 효율성에서 떨어질 수 밖에 없었다. 에라토스테네스의 체를 이용하는 경우, 인덱스를 통해 해당 수가 소수인지 아닌지를 판별하기 때문에 인덱스에 대응하는 값은 중요하지 않다. 고로 ㉠처럼 1로 채워주는 게 효율적이다.

     

    ㉡에서 Math.sqrt를 이용해주는 것도 효율성 측면에서 매우 중요하다. 

    어떤 수 n이 있을 때, 이 수는 n이하의 소수의 곱으로 구성된다. 

    즉, n은 약수로 Math.sqrt(n) 이하의 소수(n의 제곱근 이하의 소수)를 가질 것이다. ex) 49 = 7 * 7, 42 = 2 * 3 * 7

    그렇기 때문에 ㉡처럼 n의 제곱근보다 작은 수의 범위에서 소수를 찾는 것만으로도 해결이 가능하다.

    위와 마찬가지 이유로 ㉢에서 var k = j를 해줌으로써, 조금 더 효율적으로 해결할 수 있게 된다.  

     

     

     

     

    '알고리즘 문제풀이' 카테고리의 다른 글

    [APAS] Roman to Integer  (0) 2020.03.29
    [프로그래머스 Level 1] 약수의 합  (0) 2020.01.07

    댓글

Designed by Tistory.