예제 - 소수 찾기

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

이 문제를 풀려면

• 소수
• 멱집합(부분집합)
• 순열

을 알아야 했다. 물론 다른 풀이를 보면 굳이 위 개념들을 알지 않아도 풀기도 한다. 하지만 차근차근 개념을 익혀가면서 풀고 싶었기에 해당 개념들을 탐독하면서 풀었다.

결과적으로 코드는 아래와 같다.

    let numbersArr = numbers.split("");
    let includes = numbersArr.map(num => !num);
    let answer = 0;
    const dataSet = new Set();
    const primeSet = new Set();
    const isPrime = num => {
        if (num < 2) return false;
        if (num === 2) return true;
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) {
                return false;
            }
        }
        return true;
    };
    
    const permutation = (k) => {
        if(k === numbersArr.length) {
            dataSet.add(numbersArr.join(""));
        }
        for(let i = k; i < numbersArr.length; i++) {
            swap(numbersArr, k, i);
            permutation(k+1);
            swap(numbersArr, k, i);
        }
    }

    const powerset = (k, arr) => {
        if(k === arr.length) {
            let temp = "";
            for(let i = 0; i < arr.length; i++) {
                if(includes[i]) {
                    temp += arr[i];
                }
            }
            return temp !== "" && primeSet.add(parseInt(temp));
        }
        includes[k] = false;
        powerset(k+1, arr);
        includes[k] = true;
        powerset(k+1, arr);
    }

    const swap = (data, k, n) => {
        let temp = data[k];
        data[k] = data[n];
        data[n] = temp;
    }

    permutation(0);
    for(let data of dataSet) {
        powerset(0, data);
    }
    console.log(primeSet);

    [...primeSet].forEach((el) => {
        if(isPrime(el)) {
            answer++;
        }
    });

    console.log(answer);
    return answer;

큰 순서로 보면 아래와 같다.

1. numbers 에 대한 모든 순열 구하기
   1. ex) 1234 로 주어지면 1243, 1324....등이 나옴
2. 구한 순열에 대한 멱집합 구하기
   1. 1234 에 대한 멱집합은 1 2 3 4 12 ... 등이 나옴
3. 위 절차를 통해 구한 모든 경우의 수를 소수인지 검사한다.

• Set을 사용하는 이유는 중복값을 방지하기 위해서이고, 두번 사용한 이유(dataSet 과 primeSet)는 하나(dataSet)는 모든 경우의 수를 문자열로 저장한 것이고, 다른 하나(primeSet)는 숫자로 저장하기 때문이다.
  • 순열과 멱집합으로 모든 경우의 수를 만들 때 인덱스 접근을 해서 작업을 처리한다.
    • 문자열이여야만 해당 처리가 가능하다.
    • 순열로 만든 모든 문자열 경우의 수를 dataSet에 저장한다.
    • 하지만 문자열로 저장하기 때문에 011 11 를 같은 숫자로 구분하지 못한다.
    • 그래서 dataSet을 for loop를 돌며 멱집합을 수행한다. 이 과정에서 구한 모든 값은 primeSet에 숫자로 저장하여 앞서 발생한 중복 케이스를 제거한다.

소수 검사, 순열, 멱집합 를 사용하는 이유는 아래 글을 참고하면 이해될 것이다.

• 소수
• 멱집합(부분집합)
• 순열