[프로그래머스] 소수 찾기 (LV1 - JavaScript)

1. 문제

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

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

제한사항

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

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

2. 오답

풀이 전략

• 소수는 1과 자신만을 약수로 갖는 특징 사용
• 약수의 대칭성을 이용해 반복 횟수 줄이기

function solution(n) {
    let primeCount = 0;
    let i = 2;
    while(i<=n) {
        let isPrime = true;
        for(let j=2; j<=Math.sqrt(i); j++) {
            if(i % j === 0) {
                isPrime = false;
                break;
            };
        }
        primeCount += isPrime ? 1 : 0;
        i++
    }
    
    return n < 4 ? n-1 : primeCount;
}

 

테스트 케이스는 모두 통과했는데, 효율성 테스트에서 시간 초과가 3개나 나왔다....😨

찾아보니 효율성 테스트는 반복문에 의해 필요 없는 연산을 하는 경우 자주 발생한다고 한다.

 

4. 정답 풀이

풀이 전략

• 소수는 1과 자기 자신만을 약수로 갖는 특징 사용
• 1과 소수를 제외한 모든 자연수는 합성수이다. (합성수: 둘 이상의 소수를 곱한 수)
• 배열을 순회하며 자신의 배수의 인덱스에 해당하는 값(합성수)을 false로 바꾼다.
• 배열에 소수만 남는다.

function solution(n) {
    let arr = new Array(n-1).fill(true); // 길이가 n-1인 true로 채워진 배열 생성(2부터 시작)
    arr = [false, false, ...arr]; // 배열을 순회할때 인덱스를 간편하게 보기 위해 0, 1에 false 추가
    
    // n의 제곱근까지만 반복 : 약수의 대칭성 이용
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (arr[i]) { // true : 소수인 경우
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false; // i의 배수(복합수)에 false 재할당
            }
        }
    }
    
    arr = arr.filter(val => val); // 배열에서 소수(true)만 필터링
    return arr.length;
}

 

 

 

문제를 풀면서 점점 시간 복잡도의 중요성을 더 실감하고 있다. 시간 복잡도 정말 중요한데, 너무 어렵게 느껴져...😭
그래도 문제를 많이 풀다 보면 성장할 거라고 믿고, 더 열심히 해야겠다🔥🔥🔥

 

 

 

2024.09.26 - [코딩 테스트/프로그래머스] - [프로그래머스] 과일 장수 (LV1 - JavaScript)

[프로그래머스] 과일 장수 (LV1 - JavaScript)

2024.09.25 - [코딩 테스트/프로그래머스] - [프로그래머스] 모의고사 (LV1 - JavaScript)

[프로그래머스] 모의고사 (LV1 - JavaScript)