2023-09-26 알고리즘

이 게시글은 인프런 js 알고리즘 공부를 하고 배운 내용을 정리한 게시글 입니다.

1. 뒤집은 소수

문제:N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요.
예를 들어 32를 뒤집으면 23이고, 23은 소수이다.
그러면 23을 출력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다

코드

function solution(arr) {
  let answer = [];
  function isPrime(num) {
    if (num === 1) return false;
    for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
      if (num % i === 0) return false;
    }
    return true;
  }
  for (let x of arr) {
    let d = parseInt(x.toString().split('').reverse().join(''));

    if (isPrime(d)) {
      answer.push(d);
    }
  }
  return answer;
}
let arr = [32, 55, 62, 20, 250, 370, 200, 30, 100];
console.log(solution(arr));

풀이: 먼저 소수인지 아닌지 찾기 전에 , 자연수를 뒤집어서 새로운 숫자로 만들어야 한다. 그렇게 하기 위해서 나는 for of문을 돌려서 let d= 뒤집은 소수를 만들었다.
문자로 바꾼 뒤 , split을 이용하여 하나 하나 조각 내서 reverse로 역순해주고 다시 join 해주었다. 그리고 앞에 0 이 있으면 안되기 때문에 맨 앞에 parseInt 로 0을 없애주었다. 이렇게 하게 되면 d라는 새로운 소수는 23,55,26,2,52,73,2,3,1 이렇게 출력 된다.
이것을 이제 소수 찾는 함수를 만들어서 거기에다가 인자로 넣어줘서 소수인지 판별했다.
소수란? 1과 자기자신 이외의 약수가 존재하면 안된다.
예를들어 , 4는 소수다 ? X
4는 1,2,4 라는 약수가 존재한다 . 소수란 1, 자신 이외의 약수가 존재하면 안되기 때문이다.
if(num === 1) 은 1은 소수가 될수 없으므로 num 가 1이라면 false 를 반환했다.
그리고 for문을 돌려서 소수의 범위를 설정해줬는데 , 제곱근으로 하게되면 훨씬 더 범위를 줄일 수 있다.
16의 약수는 [1,16] ,[2,8],[4,4],[8,2] 이렇게 약수가 존재하는데 16의 제곱근은 4이다. 2,8에서 이미 8,2 도 걸러냈기 때문에 사실상 4까지만 돌면 되기 때문에 제곱근을 i < Math.sqrt((num)) 까지로 해줬다.
그리고 num % i === 0 이 되면 소수가 아니기 때문에 false 를 반환하고
나머지 경우는 소수이기 때문에 true 를 반환하는 소수 찾는 함수를 만들었다.