[Lv2] 소수찾기

프로그래머스

• https://programmers.co.kr/learn/courses/30/lessons/42839

나의 풀이

수도코드

• 주어진 문자열로 만들 수 있는 숫자의 순열을 구해 배열 possible에 저장한다.

  //possible은 2차원 배열
  const possible =	
  [
    [ '0', '1', '1' ], [ '0', '1', '1' ],
    [ '1', '0', '1' ], [ '1', '1', '0' ],
    [ '1', '0', '1' ], [ '1', '1', '0' ],
    [ '0', '1' ],      [ '0', '1' ],
    [ '1', '0' ],      [ '1', '1' ],
    [ '1', '0' ],      [ '1', '1' ],
    [ '0' ],           [ '1' ],
    [ '1' ]
  ]

• possible의 각 요소를 방문한다.
  • 반복문으로 요소의 인덱스값이 '0'으로 시작하는지 확인한다.
    • '0'으로 시작한다면 ''로 바꾼다.
    • '0'으로 시작하지 않는다면 반복문을 빠져나온다.
  • 배열의 값을 하나의 문자열로 만들고, 새로운 배열 str에 저장한다. (2차원 배열을 1차원 배열로 만들기 위해)
• 반복문으로 str의 요소를 확인한다.
  • 요소가 '1'이거나 이미 방문한 적이 있거나 ''인 경우는 넘어간다.
  • 그 외의 경우는 요소가 소수인지 확인한다.
    • 만약, 소수가 아니라면, isPrime을 false로 바꿔준다.
  • isPrime이 true이면, cnt++ 해준다.
  • isPrime을 다시 true로 만들어준다. (isPrime이 false로 바뀌었을 수도 있으므로 기본값을 true로 만들어준다.)
  • 확인한 요소를 또다시 확인하지 않기 위해 obj[str[i]]를 true로 저장해, 이미 방문했음을 체크한다.

//만들 수 있는 모든 숫자를 만든다. (순열)
//소수인지 판별한다.
//소수의 개수를 리턴한다.
function solution(numbers) {
    numbers = numbers.split("");
    const possible = [];
    for(let i=numbers.length; i>=1; i--){
        possible.push(...permutation(numbers,i));
    }
    return isPrime(possible);
}

//순열 구하는 함수
function permutation(arr, selectNum){
    let result = [];
    if(selectNum===1) return arr.map((v)=>[v]);
    
    arr.forEach((v, idx, arr)=>{
        const fixer = v;
        const restArr = arr.filter((_, index)=>index !== idx);
        const permutationArr = permutation(restArr, selectNum-1);
        const combineFixer = permutationArr.map((v)=>[fixer,...v]);
        result.push(...combineFixer);
    });
    return result;
}

//소수인지 확인하는 함수
function isPrime(arr){
    const str = [];
    for(let i=0; i<arr.length; i++){
        for(let j=0; j<arr[i].length; j++){
            if(arr[i][j]!=='0') break;
            arr[i][j]='';
        }
        str.push(arr[i].join(""));
    }
    let cnt = 0;
    let isPrime = true;
    const obj = {};
    for(let i=0; i<str.length; i++){
        if(str[i]==='1' || obj[str[i]] || str[i]==='') continue;
        for(let j=2; j<Number(str[i]); j++){
            if(str[i]%j===0) isPrime = false;
        }
        if(isPrime) cnt++;
        isPrime = true;
        obj[str[i]] = true;
    }
    return cnt;
}

기능별로 함수를 만들어 문제를 풀었는데, 두 개의 역할이 나누어져있어 테스트케이스가 통과하지 않았을때, 코드를 수정하는데 유용했다.

isPrime함수에서 요소의 앞자리가 0인 경우, '0011'과 '011'이 배열 str에 저장되고, obj에 저장될때에도 서로 다른 숫자로 저장되기 때문에 0으로 시작하는 경우에 대해서는 0을 모두 지워주어야했다.
이때, 순열을 구하는 함수는 변경하지 않고, isPrime에 이 부분만 추가해주면 되어서 편했다.