1. 문제
2. 풀이
3. 결과
4. 참고

1. 문제

---

소수 찾기

문제 링크

문제 설명

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

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

---

제한 사항

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

---

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

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

---

분류

• 완전 탐색
• DFS

2. 풀이

---

종이 조각으로 만들 수 있는 모든 경우의 수를 탐색하고, 그중 소수를 찾아서 개수를 세면 된다.

소수는 1과 자기 자신으로만 나누어지는 수이다.

1. numbers가 문자열로 들어오므로, 한 문자씩 분리해서 배열에 저장해준다.

2. 만들 수 있는 모든 경우를 완전 탐색한다.

   재귀를 사용하여 구현할 수 있다.

   매개 변수로 아래 값들을 전달한다.

   • set : 값 저장에 사용.
   • arr : 고정된 문자열을 제외한 값이 담긴 배열.
   • fixed : 고정된 문자열(각각의 경우에 해당).

3. 탐색하며 만들어낸 숫자가 소수일 경우 Set에 저장한다.

   소수임을 확인하는 함수를 만들어 검사한다.

4. Set에 저장된 값의 개수가 즉, 만들 수 있는 소수의 개수이다.

주의할 점

• 중복은 제외되는 것에 주의. 11과 011은 같은 숫자로 취급한다. Set을 이용하면 중복되는 값은 한 번만 저장한다.
  
• 문자형 자료를 사용해 완전 탐색하는 것에 주의 소수 검사를 하거나 값을 저장할 때, 정수로 형변환이 필요하다. 소수 검사는 자동 형 변환이 되기 때문에 괜찮을 수 있어도 값을 저장할 때 문자열로 저장하면, "011", "11" 상태로 저장되기 때문에 중복이 발생해 버린다.
  

제출

function isPrime(n) {
	if (n < 2) return false;
	for (let i = 2; i <= Math.sqrt(n); i++) {
		if (n % i === 0) return false;
	}
	return true;
}

function dfs(set, arr, fixed) {
	if (arr.length >= 1) {
		for (let i = 0; i < arr.length; i++) {
			let newFixed = fixed + arr[i];
			let copyArr = [...arr];
			copyArr.splice(i, 1);

			if (isPrime(parseInt(newFixed))) {
				set.add(parseInt(newFixed));
			}

			dfs(set, copyArr, newFixed);
		}
	}
}

function solution(numbers) {
	let nums = numbers.split("");
	let set = new Set();

	dfs(set, nums, '');
	
	console.log(set);

	return set.size;
}

3. 결과

---

테스트 1 〉	통과 (4.62ms, 30.3MB)
테스트 2 〉	통과 (7.83ms, 33MB)
테스트 3 〉	통과 (4.61ms, 30.4MB)
테스트 4 〉	통과 (6.91ms, 32.1MB)
테스트 5 〉	통과 (11.95ms, 33.7MB)
테스트 6 〉	통과 (4.60ms, 30.2MB)
테스트 7 〉	통과 (4.84ms, 30.4MB)
테스트 8 〉	통과 (12.34ms, 33.7MB)
테스트 9 〉	통과 (4.66ms, 30.3MB)
테스트 10 〉	통과 (10.11ms, 33.2MB)
테스트 11 〉	통과 (8.66ms, 32.4MB)
테스트 12 〉	통과 (4.78ms, 30.3MB)

- 정확성 : 100.0

- 합계 : 100.0 / 100.0

4. 참고

---

• https://sumin-k.medium.com/알고리즘-javascript-완전-탐색-소수-찾기-1fdcdca4f59b