프로그래머스_Level.2 소수찾기

1.문제설명

문제: 소수찾기

programmers.co.kr/learn/courses/30/lessons/42839

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

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

2.제한 조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

3.입출력 예

numbersreturn

numbers	return
"17"	3
"011"	2

 

📌나의 풀이

이 문제는 순열을 사용해서 풀어야했다. 순열을 사용하여 1부터 입력된 numbers의 길이 만큼 얻어내야한다.

function solution(numbers) {

    let num = [...numbers]

    // 순열 통해 경우의 수 구하기
    const permutation = (arr, selectNum) =>{
        let result = [];
        if(selectNum === 1) return arr.map((v)=> [v]);

        arr.forEach((v,idx,arr)=>{
            const fixer = v; //1
            const restArr = arr.filter((val, index)=> index !== idx); //2 v를 제외한 배열 만들기
            const permuArr = permutation(restArr, selectNum-1); //3 
            const combineFixer = permuArr.map((v)=> fixer + v);//4
            result.push(...combineFixer); //5
        })
        return result
    }
    
    // 소수 판별
    const checkPrime = (num)=>{
        let start = 2;
        while (start <= Math.sqrt(num)) {//Math.sqrt(num)로 반복횟수 줄이기
            if (num % start++ < 1) {//num%start ===0
                return false;
            }
        }
        return num > 1; //num이1보다 크다면 return true
    }

    let answer = []

    for(let i = 1; i <= num.length; i++){
        permutation(num, i).forEach( v=>{
            checkPrime(parseInt(v)) ?  answer.push(parseInt(v)) : answer
        })
        
    }

    //...전개 연산자
    return [...new Set(answer)].length //set을 배열로 변환

}

혼자서 코드를 고민해보다가 방법이 나오지 않아서 다른 사람들의 코드를 참고했다.

순열을 구하는 함수와 소수인지를 판별하는 함수를 만든후 사용했다.

순열을 구하는 함수인 경우에는 매개변수로 배열과 몇개의 순열을 만들어야하는지를 받는다.

 

1. foreach문을 돌면서 value를 fixer 변수에 넣고

2. value를 포함하지 않는 배열을 만든후 restArray에 저장한다..

3. restArray와 selectNum-1을 permutation함수의 매개변수로 넣는다.

   selectNum이 1이면 arr의 값을 return한다. 

4. permuArr 의 값 앞에 fixer 변수를 붙인다. 

5. .전개 연산자를 사용하여 result에 push 한다.  

 

💡배운점

• 자바스크립트로 순열 알고리즘을 작성하는 방법에 대해서 배웠다.
• 순열과 조합의 차이를 배웠다. 
• 소수를 판별하는 방법에서 Math.sqrt()를 사용하여 반복횟수를 줄이는 법에 대해서 배웠다. 

✔참고 자료

순열과 조합

coding-factory.tistory.com/607