[프로그래머스] 소수찾기(Level2) - 완전탐색 - JavaScript

1. 문제해석

- numbers의 숫자들은 종이 조각을 의미
- numbers의 요소가 0 ~ 9까지 -> 각 요소가 단일 숫자. 즉, 두 자리의 요소가 한 숫자가 될 수 없음
- 0이 맨 앞자리인 경우 생략

2. 풀이

- bfs를 이용해 만들 수 있는 모든 숫자를 찾으면서 소수 검사를 한다.
- 숫자를 조합할 때 문자로 조합하고 소수를 검사할 땐 정수로 바꿔준다.
- 만약 소수라면 정수로 변환하여 stack에 push.
- 조합한 숫자를 정수로 바꾸었을 때 stack에 존재하거나 2를 넘긴다면 무시.

function solution(numbers) {
    const stack = [];
    
    const prime = (num) => {
        const sqrt = Math.floor(Math.sqrt(num));
        
        for (let i = 2; i <= sqrt; i += 1) {
            if (num % i === 0) {
                return false;
            }
        }
        return true;
    }
    
    const makeANum = (num, idx) => {
        if (num.length === numbers.length) return;
        
        for (let i = 0; i < numbers.length; i += 1) {
            if (idx.indexOf(i) !== -1) continue;
            
            const newNum = num + numbers[i];
            
            if (stack.indexOf(parseInt(newNum)) === -1 && parseInt(newNum) >= 2) {
                const isPrime = prime(parseInt(newNum));
                
                if (isPrime) {
                    stack.push(parseInt(newNum));
                }
            }
            makeANum(newNum, [...idx, i]);
        }
    }
    
    makeANum('', []);
    
    return stack.length;
}

주의할 점은 앞서 방문한 index를 다시 방문하면 안된다는 것. 방문한 index 목록을 같이 재귀로 넘겨 주고 만약 현재 탐색할 index가 방문한 index 목록에 있다면 무시.