소수 찾기

프로그래머스 Level 2

📚 문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

📝 작성 코드

function solution(numbers) {
    var output = new Set();
    var visit = new Array(numbers.length).fill(false);
    
    for (let i = 1; i <= numbers.length; i++) {
        permutation([], numbers, output, i, visit);
    }
    
    return output.size;
}

const permutation = (array, numbers, output, n, visit) => {
    // 기저 조건
    if (array.length === n) {
        var temp = array.join(''); // 배열을 문자열로 전환
        var num = Number(temp);
        
        if (isPrime(num)) {
            output.add(num);
        }
        return;
    }
    
    // 재귀 부분
    for (let i = 0; i < numbers.length; i++) {
        if (visit[i]) continue;
        
        visit[i] = true;
        permutation([...array, numbers[i]], numbers, output, n, visit);
        visit[i] = false;
    }
}

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

output은 Set 객체로, 중복된 값이 포함되지 않으면서 소수인 것을 저장한다.

visit은 소수를 구하기 위해 순열 메서드를 사용할 때, 각 숫자가 사용되었는지 기록한다.

for문을 순회하며, 1부터 n까지의 자릿수를 가진 숫자를 permutation 메서드를 통해 number를 기반으로 생성하고, 이를 isPrime 메서드를 통해 소수인지 아닌지 판별합니다.

• 기저 조건

  • array의 길이가 n과 같아지면, 현재 만들어진 숫자를 Number로 변환한 후 소수인지 확인하고, 소수이면 output에 추가한다.

• 재귀 부분

  • 숫자 배열에서 하나씩 선택해 배열에 추가하며 순열을 생성하는 과정이며, visit 배열을 사용해 이미 선택한 숫자는 다시 선택되지 않도록 한다.

permutation 메서드가 끝나면, output의 길이를 반환하여 중복을 제외한 소수의 개수를 알 수 있다.

⏰ 걸린 시간

테스트 1 〉 통과 (0.28ms, 33.6MB) 테스트 2 〉 통과 (3.74ms, 37.2MB) 테스트 3 〉 통과 (0.10ms, 33.5MB) 테스트 4 〉 통과 (4.11ms, 37MB) 테스트 5 〉 통과 (13.30ms, 37.5MB) 테스트 6 〉 통과 (0.15ms, 33.5MB) 테스트 7 〉 통과 (0.36ms, 33.5MB) 테스트 8 〉 통과 (9.36ms, 37.4MB) 테스트 9 〉 통과 (0.22ms, 33.5MB) 테스트 10 〉 통과 (6.05ms, 37.3MB) 테스트 11 〉 통과 (1.49ms, 35.9MB) 테스트 12 〉 통과 (0.56ms, 33.7MB)