완전탐색 / 2 / 소수찾기 (JS)

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를

몇 개 만들 수 있는지 알아내려 합니다.

 

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때,

종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• umbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

문제 풀이 방법

• 문자열로 들어오는 numbers를 split("")로 1개씩 나누어준다.
• 이번에는 Set()를 사용했다.
  Set()는 중복을 허용하지 않는 값을 모아놓은 특별한 컬렉션이다.
  셋에 키가 없는 값이 저장됩니다.
• 소수인지 확인하는 함수를 선언한다.
  소수는 1과 자신만으로 나누어 떨어지는 수이다.
  이는 약수가 2개란 말이다.
  
• 그리고 완전탐색(순열)로 가능한 조합을 찾는다.
  numArr와 fixedNum을 인자로 제공하고 재귀함수를 호출하면,
  실행된 재귀함수에서는 fixed로 제공된 값에 배열의 i번째 요소 numArr[i]를 가져와 붙여줘 다음에 재공한다.
  이렇게 재귀함수를 고정되지 않은 요소가 없어질 때 까지 반복해주면
  모든 요소들을 탐생하며 만들 수 있는 모든 조합이 만들어 진다.
• 이를 소수 판별 함수를 이용해 Set에 넣어줘 반환해 주면 완성이다.

 

주의 사항

1. 소수 판별법을 알고 있어야 한다.
   자세한 내용은 아래 참고 문헌에서 참고하자
2. 순열을 이용해 완전탐색하는 방법을 인지하고 재귀함수의 사용을 주의하자

 

참고 문헌

• 맵과 셋 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/map
• 전체적인 도움을 많이 받은 블로그 (순열을 이용한 완전탐색, 소수 판별 함수)

 

코드

function solution(numbers) {
    let nums = numbers.split("");
    let answer = new Set();
    
    const isPrime = (num) => {
        if(num <= 1) return false;
        if(num === 2) return true;
        for(let i=2; i<=Math.sqrt(num); i++){
            if(num % i === 0) return false;
        }
        return true;
    }
    
    
    const getPermutation = (numArr, fixedNum) => {
        if(numArr.length) {
            for(let i=0; i<numArr.length; i++){
                const temp = [...numArr];
                temp.splice(i,1);
                if(isPrime(parseInt(fixedNum + numArr[i]))){
                    answer.add(parseInt(fixedNum + numArr[i]))
                }
                
                getPermutation(temp, fixedNum + numArr[i])
            }
        }
    }
    getPermutation(nums, '')
    
    return answer.size
}