programmers - 완전탐색 - 소수 찾기

문제 설명

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

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

function solution(numbers) {
    let answer = 0;
    let primeNumbers = [];

    const numbersArr = numbers.split("");
    
    const determinePrime = (num) => {
        let count = 0;
        for (let i = 1; i <= num; i++) {
            if (num % i === 0) {
                count++;
            }
            if (count >= 3) {
                break;
            }
        }
        if (count === 2 && !primeNumbers.includes(num)) {
            primeNumbers.push(num);
        }
    };

    const mergeNumbers = (arr, str) => {
        if (arr.length > 0) {
            for (let i = 0; i < arr.length; i++) {
                const temp = [...arr];
                temp.splice(i, 1);
                mergeNumbers(temp, str + arr[i]);
            }
            
        }

        if (str.length > 0) {
            determinePrime(+str);
        }
    };

    mergeNumbers(numbersArr, "");
    
    answer = primeNumbers.length;
    return answer;
}

1) 주어진 숫자들의 조합을 모두 찾아야 한다. 재귀함수를 사용한다.

2) 개별 조합의 경우가 나올 때마다 소수인지 판별.

python version

from itertools import permutations
import math

def check(n):
    sqrtN = math.sqrt(n) # 루트값 세팅
    
    if n < 2: # 1 이면 당연히 소수 아니다
        return False
    
    for i in range(2, int(sqrtN) + 1): # 루트값이 정수로 떨어지면 소수가 아니다
        if n % i == 0:
            return False
    
    return True

def solution(numbers):
    answer = []

    for k in range(1, len(numbers) + 1):
        permuList = list(map(''.join, permutations(list(numbers), k)))
        
        for i in list(set(permuList)):
            if check(int(i)):
                answer.append(int(i))
    
    return len(set(answer))


k = [['k', 'o'], ['j', 'n'], ['c', 'i']]
print(list(map(''.join, k))) k 배열안의 배열이나 튜플을 문자열 하나로 병합
# ['ko', 'jn', 'ci']

풀이 출처: https://ryusm.tistory.com/102
https://velog.io/@kimtaeeeny/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%86%8C%EC%88%98%EC%B0%BE%EA%B8%B0-javascript

https://eda-ai-lab.tistory.com/466