[완전탐색] 프로그래머스 '소수 찾기' level 2 - js

1. 문제

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

프로그래머스

2. 코드

순열 vs 조합?!

순열과 조합은 둘 다 서로 다른 n개에서 r개를 고르는 경우의 수를 말한다.

• 순열 : r개를 택할 때 순서대로 택하는 것  => (철원,민수)와 (민수,철원)은 다름
• 조합 : 순서와 관계없이 그냥 택하는 것 => (철원,민수)와 (민수,철원)은 같음

이 문제는 '17', '71' 등 만들 수 있는 조합에 따라 값이 달라지기 때문에 순열을 사용해야 한다!

알고리즘에서 순열을 구현할 때는 DFS를 사용해야 한다.

 

dfs 함수의 파라미터?!

• arr : 붙힌 단어를 제외한 후보 단어들을 다음 순서에 전달해줘야하기 때문
• fixed : 만들어진 고정값에 남은 단어를 붙혀야 하기 때문

 

이 문제의 포인트는 '+' 이다. 

newFixed는 문자열이므로 answer에 들어있는 값인지 아닌지를 판별할 때에는 꼭 문자열에서 정수 타입으로 바꿔주어야 한다. 이 부분을 간과하면 오답처리가 되므로!

function solution(numbers) {
    const answer = [];
    numbers = numbers.split(''); 
    
    // 소수 판별
    const isPrimeNum = (num) => {
        if(num<=1) return false;
        for (let i = 2; <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true;
    }
    
    // 순열(DFS) : 재귀 사용!
    // fixed가 고정 값 -> 고정 값을 제외한 나머지 값들을 붙혀나가기
    // '1' -> '1', '17'...
    // '7' -> '7', '71'...
    const dfs = (arr,fixed) => {
        if(arr.length >= 1){
            for(let i=0;i<arr.length;i++){
                let newfixed = fixed + arr[i];
                let newArr = arr.slice();
                newArr.splice(i,1);
                if(!answer.includes(+newfixed) && isRight(+newfixed)) answer.push(+newfixed);
                dfs(newArr, newfixed);
            }
        }
    }
    
    dfs(numbers,"");
    
    return answer.length;
}

 

복기)

3/28
4/13
6/17