[프로그래머스] 소수 찾기

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/42839
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

나의 풀이

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

function solution(numbers) {
    const answer = 0;
    const answerSet = new Set([]);
    const visited = Array.from({length: numbers.length}, () => false);
    
    function makePermutation(numberArr, currString) {
        if (isPrime(+(currString))) {
          answerSet.add(+(currString));
        }
        numberArr.forEach((item, index) => {
            if (!!visited[index]) return;
            visited[index] = true;
            
            makePermutation(numberArr,currString+item);
            visited[index] = false;
        })
    }
    
    makePermutation(numbers.split(''),'');
    console.log(Array.from(answerSet.values()))
    
    
    return answerSet.size;
}

풀이 회고

이 문제는 순열을 만드는 것과 소수를 검사하는 것, 중복을 제거하는 것 이 세가지가 가장 관건인 문제였다.

소수를 검사할 때는 제곱근까지만 비교를 하면서 소수 검사를 하였다. 이 때 제곱근까지 포함해서 검사를 해야하는데 제곱근을 포함해서 검사를 하지 않아서 오류를 해결하는데 시간이 오래 걸렸다.

중복을 제거하는 것은 set을 이용해서 해결했다.

순열을 만드는 것은 처음에는 감을 잡지 못해서 3중 for 문을 쓰려고 했는데 다른 코드를 참고한 뒤에 visited와 재귀를 이용해서 해결할 수 있었다.