문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.
효율성에서 에러가 나서 서치로 에라토스테네스의 체를 사용하여 풀 수 있다는 힌트를 얻게 되었다.
에라토 스테네스의 체는 n보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이라고 한다. (나는 ,, 몰랐다)
function solution(numbers) {
// 변수 초기화
let answer = 0; // 소수의 개수를 세는 변수
const numArr = numbers.split(""); // 입력 문자열을 문자 배열로 변환
const n = numArr.length; // 입력 배열의 길이
const ch = Array.from({ length: n }, () => 0); // 사용된 숫자를 추적하는 배열
let temp = Array.from({ length: n }, () => 0); // 현재 조합을 저장하는 임시 배열
const tempSet = new Set(); // DFS 중 생성된 고유한 숫자를 저장하는 세트
// 숫자가 소수인지 확인하는 함수
function isPrime(number) {
if (number <= 1) {
return false;
}
for (let i = 2; i <= Math.sqrt(number); i++) {
if (number % i === 0) {
return false;
}
}
return true;
}
// 조합을 생성하는 깊이 우선 탐색(DFS) 함수
function DFS(depth, length) {
if (depth === length) { // 원하는 길이의 조합이 완성된 경우
const num = parseInt(temp.slice(0, length).join("")); // 조합을 숫자로 변환
if (num !== 0 && !tempSet.has(num) && isPrime(num)) {
tempSet.add(num); // 중복을 피하기 위해 숫자를 세트에 추가, 0으로 시작하는 숫자 배제 ex)0123 -> 123
answer++; // 소수 개수 증가
}
} else {
for (let i = 0 ; i < n ; i++) {
if (ch[i] === 0) {
ch[i] = 1; // 현재 숫자를 사용된 것으로 표시
temp[depth] = numArr[i]; // 현재 숫자를 임시 배열에 추가
DFS(depth + 1, length); // 재귀적으로 다음 깊이로 이동
ch[i] = 0; // 백트래킹: 다음 반복을 위해 현재 숫자를 사용되지 않은 것으로 표시
}
}
}
}
// 다양한 길이의 조합을 생성하기 위한 반복문
for (let length = 1; length <= n ; length++) {
DFS(0, length); // 현재 길이로 DFS 시작
}
return answer; // 최종적으로 센 소수의 개수 반환
}
에러가 해결되지 않아 참조한 다른 사람의 코드
개인적으로 어려워했던 부분을 추가적으로 설명하자면.
const ch = Array.from({ length: n }, () => 0); // 사용된 숫자를 추적하는 배열
let temp = Array.from({ length: n }, () => 0); // 현재 조합을 저장하는 임시 배열
const tempSet = new Set(); // DFS 중 생성된 고유한 숫자를 저장하는 세트
이 부분은 dfs 알고리즘의 구현을 위한 배열과 세트를 초기화 하는 부분이다.
ch[i]는 숫자 배열 numArr에서 i번째 숫자가 사용되었는지를 나타낸다.
temp[depth]는 DFS의 현재 깊이에서 선택한 숫자를 나타낸다.
DFS가 진행됨에 따라 temp 배열은 조합을 형성하게 되고, DFS가 종료될 때마다 temp 배열은 초기화된다.
DFS를 통해 생성된 각 조합을 숫자로 변환하여 tempSet에 추가한다.
이렇게 하면 중복된 조합이 세트에 추가되지 않도록 하며(Set 특징), 최종적으로 소수를 찾을 때 중복을 피할 수 있다.
아직도 화살표 함수만 사용하면 코드가 어렵게 보이는 나에 대해 부가적인 설명을 붙이자면, 기본 구조는
(매개변수) => { 함수 본문 }
이고, 위 문장에선
() => 0
위와 같은 형식으로 쓰였다.
이 함수는 매개변수가 없고, 항상 0을 반환한다. Array.from 메서드의 두 번째 인자로 사용되어 배열의 각 요소를 초기화하는 데 활용된 모습이다.
Array.from은 유사 배열 객체나 반복 가능한 객체를 배열로 변환하는 메서드이다. 첫 번째 인자로는 변환할 대상 객체를, 두 번째 인자로는 매핑 함수를 받는다.
코드에서 사용된 형식은
Array.from({ length: n }, () => 0)
이러한 형태인데, 길이가 n인 배열을 생성하고, 각 요소를 화살표 함수에 따라 초기화 하는 것이다.
for (let i = 0 ; i < n ; i++) {
if (ch[i] === 0) {
ch[i] = 1; // 현재 숫자를 사용된 것으로 표시
temp[depth] = numArr[i]; // 현재 숫자를 임시 배열에 추가
DFS(depth + 1, length); // 재귀적으로 다음 깊이로 이동
ch[i] = 0; // 백트래킹: 다음 반복을 위해 현재 숫자를 사용되지 않은 것으로 표시
}백트래킹이란, 문제를 해결하기 위해 탐색하는 도중에 현재 경로가 해결책으로 이어질 것 같지 않으면, 그 경로를 그만두고 이전 단계로 돌아가 다른 경로를 탐색하는 기법이다.
ch 배열은 숫자가 사용되었는지 여부를 추적하는 배열로, 각 숫자의 사용 여부를 표시한다.
temp[depth] = numArr[i];: 현재 깊이 depth에서 사용된 숫자를 temp 배열에 추가한다. temp 배열은 현재까지의 조합을 나타내며, 각 깊이에서 어떤 숫자가 선택되었는지를 기록해준다.
DFS(depth + 1, length);: 현재까지의 깊이를 1 증가시켜 재귀적으로 다음 깊이로 이동한다. 이 부분이 dfs의 핵심이며 재귀 호출을 통해 깊이를 증가시키며 가능한 모든 조합을 탐색한다.
ch[i] = 0;는 이전에 사용했던 숫자를 다시 사용할 수 있도록 ch 배열에서 해당 숫자를 사용되지 않은 것으로 표시함으로써 이전 단계로 돌아가서 다른 숫자를 선택하여 탐색할 수 있다.
