[프로그래머스_완전탐색] 소수찾기

프로그래머스

 

[문제 요구 사항]

- 한 자리 숫자가 적힌 종이 조각이 흩어져있습니다. 이 종이 조각으로 만들 수 있는 숫자 중 소수는 몇 개인지 알아내세요

 

[문제 아이디어]

1. 한 자리 숫자들을 순열로 배열해서 만들 수 있는 모든 숫자를 찾는다.

2. 해당 숫자가 소수인지 판단한다.

  - 소수를 판단할 때는 아리스토텔레스의 체를 사용한다. DP 처럼 미리 만들어두고 재활용해야만 최적화가 될 거 같다.

 

시간복잡도 :

- 순열 사용 시, O(n!) 의 시간 복잡도를 가진다.

- 소수 테이블 생성 시, O(nlogn)의 시간 복잡도를 가진다.

 

합치면 O(n!)이다.

 

공간복잡도 : 

- 소수 테이블을 만들 때, 배열을 저장할 공간 n개가 필요하다. 즉, O(n)이다.

 

[내 풀이]

function solution(numbers) {
    
    const maxNumber = Number(numbers.split('').sort((a,b) => b-a).join(''))
    const oddDp = Array.from({length : maxNumber +1}).fill(0)
    oddDp[0] = 1
    oddDp[1] = 1
    
    function makePrimeTable() {
        for (let i =2; i< Math.sqrt(maxNumber); i++) {
            if (oddDp[i] === 0) {
                for (let j = i*2; j <= maxNumber; j+=i){
                    if(oddDp[j] ===0) {
                        oddDp[j] = 1    
                    }  
                }
            }
        }
    }

    makePrimeTable()
    
    function checkPrime(x) {
        if (oddDp[x] === 0) {
            return true
        } 
        return false
    }
    
    
    var answers = [];
    
    function permute(arr, m = []) {
        if (m.length > 0) {
            const translateNum = parseInt(m.join(''), 10)
            if (checkPrime(translateNum)) {
                answers.push(parseInt(m.join(''), 10));
            }
            
        } 
            for (let i = 0; i < arr.length; i++) {
                const current = arr.slice();
                const next = current.splice(i, 1);
                permute(current, m.concat(next));
            }
        
    }
    
    permute(numbers.toString().split(''))

    return Array.from(new Set(answers)).length;
}

- 소수테이블을 생성한다.

- 순열을 돌려서, 숫자를 생성하고 소수테이블을 이용하여 소수인 지 체크한다.

- 중복이 있을 수 있으니 Set으로 중복을 제거한다.

 

풀이 결과 : 잘 푼 줄 알았다. 근데, 몇 개의 시간이 확 튄다.

 

[2번 풀이 = 다른 분 풀이 적용]

function solution(numbers) {
    
    function checkPrime(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;
    }

    
    var answers = [];
    
    function permute(arr, m = []) {
        if (m.length > 0) {
            const translateNum = parseInt(m.join(''), 10)
            if (checkPrime(translateNum)) {
                answers.push(parseInt(m.join(''), 10));
            }
            
        } 
            for (let i = 0; i < arr.length; i++) {
                const current = arr.slice();
                const next = current.splice(i, 1);
                permute(current, m.concat(next));
            }
        
    }
    
    permute(numbers.toString().split(''))

    return Array.from(new Set(answers)).length;
}

- 다른 분의 풀이에서 소수 체크를 매 번 별도로 진행하여서 적용해봤는데 시간이 튀지 않고 빠르게 변했다.

- CheckPrime의 시간 복잡도를 계산했을 때, 내가 더 유리하다. 근데 왜 시간이 이렇게 나오는 지 모르겠다. n의 7이라 비슷하게 나올 수는 있어서 그런가 보다.

 

 

[배울 점]

- 순열 짜는 코드가 안 익숙하다. 코테 잘 보려면 이 부분 숙련도가 필요하다.

- 순열 시간 복잡도가 너무 높아서 백트래킹을 잘 하는 법을 공부해야할 거 같다.