[완전탐색] 뒤집은 소수

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

N개의 자연수가 입력된다.

각 자연수를 뒤집은 후 그 수가 소수이면 뒤집힌 수를 출력한다.

예를 들어 32가 입력된다면 뒤집은 수 23은 소수이므로 23을 출력한다.

 

 

👉 입력

N개의 자연수가 입력된다.

 

 

👈 출력

소수를 입력된 순서대로 출력한다.

 

 

💡 사용된 개념

소수

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다.

 

먼저 소수의 정의를 가지고 구현한 소수를 판별하는 코드는 다음과 같다.

 

function isPrime(num) {
    if (num === 1) return false;

    for (let i = 2; i < num; i++) {
        if (num % i === 0) return false;
    }

    return true;
}

 

1이 입력으로 들어왔을 때 1은 소수에 해당하지 않으므로 바로 false가 리턴된다.

1이 아닌 수가 입력으로 들어왔을 때 i는 2부터 입력으로 들어온 수까지 for문을 돌며 이 수가 나누어 떨어지는 값이 있는지 판별한다.

if문에 하나라도 걸리게 되면 소수의 정의와 일치하지 않으므로 false가 리턴된다.

그렇지 않으면 이 수는 소수이다.

 

만약 16이라는 값이 입력으로 들어왔다면 16은 소수가 아니므로 if문 조건에 걸려 false가 리턴된다.

이때, 16의 약수는 1, 2, 4, 8, 16이다.

이는 이렇게도 표현할 수 있다.

• 1 * 16
• 2 * 8
• 4 * 4
• 8 * 2
• 16 * 1

4를 기준으로 앞뒤가 대칭적이다.

 

따라서 어떠한 값이 소수가 되는지를 판별하려면 가운데 약수까지만 나누어 떨어지는지 판별해도 동일한 결과를 얻을 수 있다.

 

function isPrime(num) {
    if (num === 1) return false;

    for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
        if (num % i === 0) return false;
    }

    return true;
}

 

결론적으로 소수를 판별하기 위해서는 i가 2부터 입력으로 들어온 값의 제곱근까지만 for문을 돌며 해당 수가 나누어 떨어지는 경우가 있는지 판별하면 된다.

 

 

📝 풀이

 

function isPrime(num) {
    if (num === 1) return false;

    for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
        if (num % i === 0) return false;
    }

    return true;
}

function solution(arr) {
    let answer = [];
    for (const a of arr) {
        let num = parseInt(a.toString().split('').reverse().join(''));
        if (isPrime(num)) answer.push(num);
    }
    return answer;
}

let arr = [32, 55, 62, 20, 250, 370, 200, 30, 100];
console.log(solution(arr));

 

값을 뒤집기 위해서 입력으로 들어온 배열 arr을 순회하면서 요소를 문자형으로 바꾸어 쪼개고 뒤집은 후 다시 합친 것을 정수로 바꾸어주었다.

즉, 32 -> '32' -> ['3', '2'] -> ['2', '3'] -> '23' -> 23의 순서를 거친 것이다.

그리고 이 수가 소수인지 판별한 후 소수가 맞다면 answer에 넣어주었다.