[프로그래머스] level1 : 소수찾기 (생각보다 많이 헤맨 문제)

1. 문제 설명

• 문제 설명 보러가기

2. 문제 해석 

문제 자체는 쉽다.

주어진 숫자 n이 10이라고 가정했을 때, 1~10 까지의 숫자들 중 소수가 몇개인지를 리턴하는 문제다.

소수란, 1과 자기 자신, 이렇게 2개의 약수만 가진 수를 말하며 0,1은 제외된다. 소수로는 2,3,5,7,11... 등이 있다.

이 문제를 푸는건 쉽지만, 또한 쉽게 성능 테스트에서 fail이 난다. 왜냐하면 주어진 숫자 n의 최댓값이 1,000,000으로 상당히 큰 값이 주어지기 때문이다.

이렇게 대량의 데이터에서 소수를 찾을 때, 에라토스테네스의 체 알고리즘을 사용하면 성능을 챙길 수 있다.

이 문제를 해결하는 데 3일이 넘게 걸렸는데.. 성능 fail을 해결하지 못해 정답을 검색하다가 근의 공식을 활용하여 (Math.sqrt()) 푼 답을 참고하라는 조언을 받고 루트부터..근의 공식까지 공부하다가 (중딩 때 이미 수학 포기한 사람) 도저히 근의 공식을 활용한 솔루션을 이해할 수 없어서 오래걸렸다. 

결론은, 근의 공식따위를 활용하지 않고 에라토스테네스의 체 알고리즘을 활용하여 간단하게 해결했다.

 

3. 문제 풀이

에라토스테네스의 체를 먼저 알아보자. (아주 간단하다)

이 그림을 보면, 제일 먼저 만나게 되는 숫자는 2다. (1은 어차피 소수가 아니므로 제외하기 때문에)

2를 제외하고 2로 나누었을 때 0이 되는 모든 숫자를 지운다. (4, 6, 8, 10, 12, 14, 16...)

그 다음 만나는 숫자는 3이다. 3을 제외한 3으로 나누었을 때 0이 되는 숫자를 모두 지운다. 이 때 앞서 이미 지워졌던 숫자들은 건너 뛴다. 

그러면 3으로 지워지는 숫자는 9, 15,.... 등이 된다. 

그 다음으로 만나게 되는 숫자는 5다. 왜? 2와 3으로 나누었을 때 0이 되는 숫자는 모두 지웠으므로, 앞서 지워졌던 4는 건너 뛰기 때문이다.

이 과정을 반복한 뒤, 지워지지 않은 숫자들이 모두 소수에 해당한다.

코드로 보자.

function solution(n) {
    const numArr = [0,0] //0, 1은 소수가 아니므로 0을 미리 채워놓는다.
    let result = 0;
    
    //1. numArr에 숫자 2부터 n까지의 숫자를 채워준다.
    for(let i=2; i <=n; i++){
        numArr[i] = i
    }
    
    //2. numArr에 든 숫자에 차례로 0을 채울건데, 0이란 지워진 숫자를 의미한다.
    //안쪽 for문에서 j에 i+i 값을 넣는 이유는 i의 배수를 모두 지우기 위해서다.
    //0이 채워져 있다면 이미 지워진 숫자이므로, continue로 단계를 뛰어넘는다.
    for(let i=2; i<=n; i++){
        if(numArr[i] === 0) continue;
        for(let j = i+i; j<=n; j= j+i){
            numArr[j] = 0;
        }
    }
    
    //3. 소수를 제외한 모든 값에 0이 채워진 numArr의 for문을 돌며, 
    //0이 아닌 값이 있을 때마다 result값을 1씩 더한다.
    for(let i=2; i<=n; i++){
        if(numArr[i] !== 0) ++result;
    }
    return result;
}

 

for문이 너무 많이 등장해서 성능이 낮을 것 같지만 이렇게 푼 문제가 근의 공식으로 해결한 솔루션보다 성능이 우수했다. 근의 공식을 활용한 솔루션을 잘 이해하진 못했으나, 어쨌든 탐색해야 하는 양이 에라토스테네스의 체 알고리즘보다 더 많다는 건 보였다. 

왜냐하면 처음 2의 배수 지우기로 상당히 많은 숫자들이 제거가 된다. 그 다음 3, 5.. 남은 숫자들의 배수를 지우는 과정에서도 마찬가지로 많은 숫자들이 제거되어, 탐색해야 하는 데이터의 양이 쭉쭉 줄어들기 때문이다.

보기에도 훨씬 이해하기 쉽고 단순한 이 풀이가 마음에 든다.

 

결론

수포자에게도 늘 희망이 있다.