[JS] 소수 찾기

 

 

난이도: Lv. 2

정답률: 53%

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

프로그래머스

 

 

알고리즘

1. 찾은 소수를 저장할 Set을 선언한다.
   • 이 Set은 동일한 수가 정답으로 여러 번 카운팅 되는 것을 막아준다. 
   • "011"에서 11이라는 수는 두 번 발생하지만 카운팅은 한 번만 해야 하는 게 그 예시다.
2. 숫자 하나와 numbers 문자열에서 어떤 문자가 이미 사용되었는지 표시해 주는 bitArr 배열을 파라미터로 넘겨주어 깊이 우선 탐색을 시작한다.
   1. 소수인지 판별해야 하므로 문자열을 숫자로 변환한다.
   2. 소수인지 판별하고, 소수일 경우 Set에 존재하는지 확인한다. 동일한 수가 한 번만 정답으로 카운팅 되게 하기 위함이다.
   3. Set에 존재하지 않는 수라면 정답으로 카운팅된 적이 없음을 의미하므로 Set에 그 수를 넣고 정답을 1 증가시킨다.
   4. bitArr에서 원소가 0이면 사용되지 않은 문자임을 의미한다. 따라서 비트가 0인 문자를 현재 문자열에 붙이고, 해당 비트를 1로 만들어 재귀를 한다. 재귀 함수를 실행시키고 나서 반드시 바꿨던 비트를 다시 0으로 바꿔줘야 한다. bitArr의 모든 비트가 1이 되면 재귀를 종료한다.
      • numbers가 "123"일 때 currStr이 "1"인 상태라고 생각해 보자. dfs("12", [1, 1, 0])을 실행할 것이다. 이후에 해당 비트를 0으로 바꿔주지 않으면 dfs("13", [1, 1, 1])이 실행된다. 우리가 원하는 bitArr는 [1, 0, 1]이기 때문에 비트를 0으로 다시 바꿔주는 과정이 필요하다.

 

 

코드

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

    return true;
}

function solution(numbers) {
    let answer = 0;
    const primeSet = new Set();

    function dfs(currStr, bitArr) {
        const currNum = Number(currStr);
        isPrime(currNum) && !primeSet.has(currNum) && primeSet.add(currNum) && answer++;

        for (let i = 0; i < bitArr.length; i++) {
            if (!bitArr[i]) {
                bitArr[i] = 1;
                dfs(currStr + numbers[i], bitArr);
                bitArr[i] = 0;
            }
        }
    }

    for (let i = 0; i < numbers.length; i++) {
        dfs(numbers[i], Array.from({ length: numbers.length }, (value, idx) => idx === i ? 1 : 0));
    }

    return answer;
}

 

 

주저리

고난1

처음에는 Set에 이미 존재하는 수면 더 이상 아래로 내려가지 않도록 했다. 숫자가 1~9만 있었으면 그렇게 해도 됐을 텐데 0도 있을 수 있어서 틀린다는 것을 깨달았다.

고난2

테케 3개가 통과가 안되길래 2를 소수로 판별하지 않고 있나? 해서 설레하면서 다시 해봤는데 그거 때문이 아니었다. 멋슥

질문하기 탐방하다가 제곱수 때문인걸 알아서 코드 찬찬히 다시 읽어보니 isPrime 함수에 반복문 조건에 등호를 안 깔았다.

나는 바보