[JS알고리즘] 뒤집은 소수

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

function solution(arr){
  let answer=[];
  for(let x of arr){
    let res=0;	//받은 값의 reverse된 값을 저장한다. 뒤집어진 소수가 답이기 때문에 원본을 저장할 필요가 없다
    while(x){
      let t=x%10;
      res=res*10+t;
      x=parseInt(x/10);
    }
    if(isPrime(res)) answer.push(res);
  }
  return answer;
}


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

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문으로 돌리는 s에서 s[i] 와 s[i+1]의 값이 동일한지 비교하고 같으면 cnt를 증가(cnt는 갯수이기 때문에 무조건 1부터 시작한다)
cnt가 1보다 크면 answer에 더한다
res에 x를 reverse한 수를 넣어주기 위해 변수를 설정한다
while문은 x를 거꾸로 뒤집는 과정이다. x가 0이 될 때까지 while문을 돌리고 0이되어 break될때까지 계속해서 도는데, 그 과정을 하나하나 뜯어보자. 숫자 307을 예로 들어보자.
1. (while첫번째. x=307)
  1. t = x % 10 는 t는 x의 일의자리라는 뜻이다.
    현재 x는 307이고 10으로 나눈 나머지는 7이기 때문에 t는 7로 307의 일의자리숫자이다.
    res는 0 * 10 +7 이기 때문에 7이다.
  2. parseInt(x/10) 는 x의 몫. 307을 10으로 나누면 30이 몫이므로 x는 30이다.
2. (while두번째. x=30)
  1. t는 30의 일의 자리 이므로 0이다
  2. res는 7이므로 7 * 10 + 0 = 70이다.
  3. x는 30을 10으로 나눈 몫이므로 3이다.
3. (while세번째. x=3)
  1. t는 일의자리 수이므로 3이다.
  2. res는 70이므로 70 * 10 + 3 = 703 이다.
  3. x는 3을 10으로 나눈 몫이므로 0이다.
4. break된다
만들어준 isPrime 함수를 사용하여 소수인지 확인한다.
1. 소수판별법(하 이거 언제적 개념이지…. 근 15년만인것 같은데…)
2. 1과 자기자신의 수를 제외한 수 중에(1과 자기 자신은 약수이기 때문에) 약수가 있으면 소수가 아니다
3. ex)15의 소수를 알기 위해서는 1과 15를 제외한 2-14의 수 중에 약수가 없는 것을 고른다
4. 본인을 제외한 수중 가장 큰 약수는 본인 자신의 수의 /2를 한 숫자이므로
5. parseInt(Math.sqrt(num)) (넘어온 숫자의 제곱근까지만 돌아라) 대신에 parseInt(num/2) 를 사용해도 무방하다
6. 그렇게 if(num%i===0) return false; 약수가 발견되면 소수가 아니라는 것이니 false 리턴한다.

reverse함수 사용하는 경우

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;
  }
  function solution(arr){
    let answer=[];
    for(let x of arr){
    	let res=Number(x.toString().split('').reverse().join(''));
    	if(isPrime(res)) answer.push(res);
    }
    return answer;
  }

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

Number 나 parseInt 를 사용하지 않으면 숫자를 뒤집었을때 03 같이 0이 앞에 문자열로 인식되므로 숫자화 시켜주어야 한다

내장함수를 사용하면 확실히 조금 더 편하게 할 수 있지만,

첫번째 경우는 원리를 정확히 알아야만 사용 가능한 방법이다. 첫번쨰 방법은 알아두어야 할 방법!

inflearn 자바스크립트 알고리즘 강의 내용 =)

Share this post