Programmers - 완전탐색 > 소수 찾기

내 풀이

일단 가장 먼저 순열, 조합이 생각났고 그 외에 딱히 다른 풀이법이 떠오르지 않았다. 문제 컨셉이 완전탐색인 것도 한 몫 했다. L2문제지만 1시간이 넘게 걸려 결국 풀지 못했다.

1. numbers를 쪼개서 배열에 집어넣는다. "17" -> [1, 7]
2. 배열의 조합 케이스를 구한다.
3. 각각의 조합 케이스에 순열 케이스를 구한다.
4. 순열 케이스의 각 자리수를 더했을 때 소수면 result.push()

모범 답안

Set api를 사용하여 원소를 쉽게 찾고, 추가하고, 삭제할 수 있다. 특정 원소를 찾는 방법이 생각보다 까다로웠는데 Set api를 숙지하면 활용할 곳이 많을 것 같다. 재귀함수를 사용해서 문제를 해결하였는데 이 방법이 알고리즘적으로 효율적인지는 의문이다.

1. numbers string을 쪼개서 배열에 넣는다.
2. 중복되는 값이 Set에 존재하지 않을 경우 Set에 넣는다. (중복 방지)
3. 모든 경우를 재귀적으로 탐색하면서 isPrime일 경우에만 answer++한다.

function solution(numbers) {
    var answer = 0;
    var n = numbers.split('');
    var nums = new Set()
    
    combi(n,'');

    function combi(a, s) {
        if (s.length > 0) {
            if (nums.has(Number(s))=== false) {
                nums.add(Number(s));
            console.log(Number(s))
                if (chkPrime(Number(s))) {
                    answer++;
                }
            }
        }
        if (a.length > 0) {
            for (var i = 0; i< a.length; i++) {
                var t = a.slice(0)
                t.splice(i,1);
                //console.log(t)
                combi(t,s + a[i]);
            }
        }
    }

    function chkPrime(num) {
        if (num < 2) return false;
        if (num === 2) return true;
        for (var i = 2; i <= Math.sqrt(num); i++) {
            if (num%i===0) return false;
        }
        return true;
    }

    return answer;
}

얻어갈 부분

• Set api 사용
• 재귀함수도 하나의 해결책