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

# 문제 원문

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers / return

"17"	3
"011"	2

출처

# 문제 풀이

소수를 찾는건 소수라는 개념을 알고 있으면 그렇게 어렵지 않지만, 소수인지 검증할 숫자를 맞추는건 단순히 반복문으로는 하기 힘들다. 그렇기에 DFS 깊이 우선 탐색이 필요하게 되는데 (사실 BFS도 별차이 없겠지만.. 어차피 다 탐색하는 거니) DFS 구현 하는 법을 자세히는 모른다.. 재귀 함수를 통한 stack에 push pop 하는 구조를 DFS문제 몇번 풀다보니 익숙해져서 해당 구조는 그냥 만들어서 쓰는데 정말 상세하게 모든걸 파악하고 있지 않아서 응용이 가능할지 의문이라는게 흠이다. 당장 (DFS와 BFS가 뭔 차이인지 부터 헷갈리니까) 이런 점에서 부족한 점을 느껴서 따로 DFS, BFS를 공부해야 할 필요성을 느꼈다. 여러가지 구조로 만들어 보면 조금 잘 이해가 될려나..?

 

# 솔루션 플로우

1. 입력 받은 문자열 numbers를 배열로 만들어준다.

2. 만들어진 배열을 DFS 진행한다.

3. numbers array에서 하나씩 꺼내서 stack에 넣었다 뺐다 하면서 비교하면서 모든 노드를 방문한다.

4. 그렇게 방문한 노드들이 소수인지 검증하고 소수이면서 구한 적이 없다면 result 카운트를 추가해준다.

5. 얻어진 result를 반환한다.

1. DFS

function solution(numbers) {
    const result = new Set();

    combination(Array.from(numbers));

    return result.size;

    function combination(numbers, stack = []) {
        const num = parseInt(stack.join(''));
        if (stack.length > 0 && !result.has(num) && checkPrime(num)) {
            result.add(num);
        }

        if (numbers.length > 0) {
            numbers.forEach((current, idx) => {
                stack.push(current);
                combination([...numbers.slice(0, idx), ...numbers.slice(idx + 1)], stack);
                stack.pop();
            });
        }

        function checkPrime(num) {
            if (num < 2) return false;
            for (let int = 2; int < num; int++) {
                if (num % int === 0) return false;
            }
            return true;
        }
    }
}