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

https://programmers.co.kr/learn/courses/30/lessons/42839

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

문제 설명

 

문제 풀이

1. 재귀를 통해 순열의 모든 경우를 다 구할 수한다.

• vistied로 이미 한번 사용된 문자에 대해서는 체킹한다.
• 똑같은 인덱스에 숫자 반복하지 않게 확인하는 작엄

2. 완성된 숫자에 대해 소수인지 탐색(아리스토체 방식) 한다

• 이때, 1과 0에(문자열이 0으로 시작할 때) 대해서는 예외 처리해준다.

3. 소수라면 해당 문자가 이미 만들어진 것인지 확인한다.

• 만들어 지지 않았다면 카운팅하고 배열에 소수를 추가한다.
• 똑같은 숫자가 여러개 일 경우 같은 숫자가 여러번 만들어 질 수 도 있기 때문

 

function solution(numbers) {

    let visited = [0, 0, 0, 0, 0, 0, 0, 0];
    let made = [];


    function check_sosu(num) {

        if (num == 1 || num[0] == '0') {
            //1이나 문자가 0으로 시작할 경우('011') 걸러줌
            return false;
        }
        for (var i = 2; i <= Math.sqrt(num); i++) {
            //아리스토체 방식 소수 체킹
            if (num % i == 0) {
                return false;
            }
        }
        return true;

    }


    function go(cnt, indx, numbers, num) {

        if (cnt && check_sosu(num) && !made.includes(num)) {
            // 아예 아무것도 안 만들어 진 상황 부터 시작하기때문에 cnt=1이상일때 부터 확인해준다.

            made.push(num);
            //소수이고 같은 숫자가 만들어진 적없으면 추가
        }

        if (cnt == numbers.length) {
            //최대 numbers길이 넘어가지 않게 종료
            return;
        }

        for (var i = 0; i < numbers.length; i++) {
            if (visited[i]) continue;
            visited[i] = 1;
            go(cnt + 1, i, numbers, num + numbers[i]);
            visited[i] = 0;
        }
    }


    go(0, 0, numbers, '');
    return made.length;
}