완전탐색 - 소수 찾기

문제

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예

numbersreturn

"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

접근 및 풀이

완전 탐색 문제. dfs로 처음부터 접근했으나 어떻게 구현할 지 막막했다. 다른 사람의 팁 중 재귀에 대한 힌트가 있어서 차용했다. 익숙하지 않아서 시간이 엄청 걸렸다.

풀이는 다음과 같다.

현재 숫자와 남은 숫자를 나눈다. 남은 숫자에 초기값을 모두 넣는다. 남은 숫자에의 for문은 해당 원소를 고정하고 나머지 원소들을 탐색한다는 의미이다. 이 때 탐색할 때마다 소수 체크와 중복 체크를 한다.

재귀가 너무 어렵다.

코드

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

function solution(numbers) {
  let primes = [];

  numbers = numbers.split("");
  dfs([], numbers);
  return primes.length;
  function dfs(num, rest) {
    rest.forEach((e,index,origin)=>{
      num.push(e);
      let t = +num.join('');
      if (num[0] != 0 && isPrime(t) && !primes.includes(t)) primes.push(t);
      
      let temp = [...origin];
      temp.splice(index,1);
      let ntemp = [...num];
      dfs(ntemp, temp);
      num.pop();
    })
  }

}

출처 : https://programmers.co.kr/learn/courses/30/lessons/42839?language=javascript