프로그래머스-소수 찾기

개요

이번 문제는 컴퓨터의 성능을 이용한 완전 탐색 관련 문제이다. 큰 어려움은 없었으나 for문 제한 조건에 = 하나 빼먹어서 시간을 좀 잡아먹었다.

문제 링크

• 프로그래머스-소수 찾기

분류

• Level 2
• 완전탐색

요점

• 11과 011은 같은 숫자로 취급됨
• 중복을 제거해야함

어려웠던 부분

• 없음

코드(javascript)

function solution(numbers) {

    numbers = numbers.split('');
    let result = [];

    let swap = function (arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    let perm = function (arr, depth, n, k, result) {
        if (depth == k) { // 한번 depth 가 k로 도달하면 사이클이 돌았음. 

            let tArray = [];
            for (let i = 0; i < k; i++) {
                tArray.push(arr[i]);
            }
            //console.log(tArray);
            result.push(tArray);
            return tArray;
        }

        for (var i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k, result);
            swap(arr, i, depth);
        }
    }

    let n = numbers.length;

    //모든 순열을 구함
    for (let i = 1; i <= n; i++) {
        perm(numbers, 0, n, i, result);
    }

    //배열 -> 숫자로 변환
    result = result.map(value => {
        return Number.parseInt(value.join(''));
    });

    //소수 판별
    result = result.map((value) => {
        let primeFlag = true;
        if (value === 1 || value === 0) { primeFlag = false }
        else {
            for (let i = 2; i <= Math.sqrt(value); i++) {
                if (value % i === 0) {
                    primeFlag = false;
                }
            }
        }
        if (primeFlag) { return value }
    }).filter(value => value !== undefined);


    //중복 제거를 위해 Set 사용
    return new Set(result).size;
}

• 코드 설명 우선 입력된 numbers를 split하여 배열로 변환후 경우의 수를 구한다.

• 그후 경우의 수를 모두 숫자로 변환하여 소수여부를 확인한다.

• 소수만 남은 배열을 Set에 넣어 중복을 제거함

• Set의 크기를 반환함.