꒰ྀི 04. 프로그래머스:: 소수 찾기

문제 설명

 

한 자리 숫자가 적힌 종이 조각이 흩어져있음.

모든 숫자 중 소수가 몇 개인지 확인해야함

 

자료 구조

 

가능한 모든 경우를 탐색해야하기 때문에 완전 탐색을 사용하였음.

주어진 숫자 조각으로 만들 수 있는 소수를 모두 확인해야 함.

 

해결 과정

 

1. 숫자 조각으로 만들 수 있는 조합 생성

  - 단, 모든 조합을 생성하며 생기는 중복을 제거해야함. (Set 활용)

자바스크립트 세트(Set) 완벽 가이드

 

2. 생성된 숫자가 소수인지 확인

  

3. 소수 개수 반환

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

function getPermutations(arr, length) {
    if (length === 1) return arr.map(v => [v]);
    const permutations = [];
    arr.forEach((v, i) => {
        const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
        const restPerms = getPermutations(rest, length - 1);
        const attached = restPerms.map(p => [v, ...p]);
        permutations.push(...attached);
    });
    return permutations;
}

function solution(numbers) {
    const numberArr = numbers.split('');
    const permutationsSet = new Set();

    for (let length = 1; length <= numberArr.length; length++) {
        const permutations = getPermutations(numberArr, length);
        permutations.forEach(perm => {
            const num = parseInt(perm.join(''), 10);
            permutationsSet.add(num);
        });
    }

    let primeCount = 0;
    permutationsSet.forEach(num => {
        if (isPrime(num)) {
            primeCount += 1;
        }
    });

    return primeCount;
}

 

isPrime 함수
  - 주어진 숫자가 소수인가?
getPermutations
  - 주어진 배열에서 특정 길이의 순열 생성 재귀 함수

 

완전 탐색을 이용해 가능한 모든 숫자 조합을 생성하고,

각 숫자가 소수인지 확인하는 방법을 사용해야 했다.

 

모든 경우를 탐색하기에 정확한 결과를 보장하는만큼 효율성에 신경써야 했으며

모든 숫자 조합 생성 시 발생하는 중복 제거를 Set 자료구조를 이용해 제거해주어야했다.

 

재귀 함수를 이용하므로 효율성 테스트를 걱정했는데,

무사히 통과할 수 있었다.