42839. 소수 찾기

코딩테스트 연습 - 소수 찾기

문제 유형	난이도	걸린 시간	해결 유무(✅/❌)
완전탐색	lv.2	2시간	✅

설계 방법

• 문자열 배열이 주어지면 모든 순열을 찾는 함수를 이용한다.

• ex) ['0', '1', '1'] => [ '0', '1', '1', '01', '01', '10', '11', '10', '11', '011', '011', '101', '110', '101', '110' ]

• 모든 순열을 Number 함수로 숫자로 만든다. (이 과정에서 앞의 0이 사라진다.)

• 각 숫자가 소수이면 소수 Set에 추가한다. (이 과정에서 중복이 제거된다.)

코드

function solution(numbers) {    const primeNumbers = new Set();
    for (let i = 1; i <= numbers.length; i++) {        getPermutation(numbers.split(''), i)            .map(Number)            .forEach((number) => {                if (isPrime(number)) {                    primeNumbers.add(number);                }            });    }
    return primeNumbers.size;}
function getPermutation(arr, n) {    if (n === 1) {        return arr;    }
    return arr.reduce((perms, cur, idx) => {        getPermutation(            [...arr.slice(0, idx), ...arr.slice(idx + 1)],            n - 1,        ).forEach((perm) => {            perms.push(cur + perm);        });
        return perms;    }, []);}
function isPrime(num) {    if (num < 2) return false;    if (num === 2) return true;    for (let i = 2; i <= Math.sqrt(num); i++) {        if (num % i === 0) return false;    }    return true;}

시간 복잡도

• 순열 : O(N!)

어려웠던 점

• 모든 순열 찾기, 소수 찾기, 중복 제거, 앞의 0 제거 등의 기능을 분리할지 합성할지 고민이 길어졌다.

• 모든 순열 찾기 함수를 작성하는데 어려움을 겪었다.

• 모든 순열을 검색하는 것까지 시간 복잡도를 허용할 것인지 고민을 많이 했다.

  • 제한 사항을 보고 어느 정도의 시간 복잡도가 통과할 것인지가 예측 가능한지 궁금하다.

• 10자리 수까지 테스트 해보았는데, 반복문 안에서 재귀함수를 n 깊이만큼 들어갔다가 빠져나와서 그런지 stack overflow는 발생하지 않았다.

• 10자리 수 테스트가 8분 정도 걸렸다.

참고자료

• Find All Permutations of a String in Javascript