[완전 탐색] 소수 찾기

순열 구현을 한참하다가 굉장히 오래걸렸던 문제이다.

swap으로 하면 굉장히 간단해보이던데 다르게 풀어본다고 시간을 엄청 썼다.

다른 분들의 코드를 참고해도 순열은 너무 어려워서 완전 탐색 부분만 내일 한 번 다시 다뤄봐야겠다.

https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-21df4b536349

 

결국 재귀로 접근하면 기본 원리는 모두 같다. 

다른 숫자들은 고정하고 단 두가지 숫자의 순서를 바꾸는 과정을 반복해나가는 일이다.

 

그러나 트리처럼 하나의 재귀함수에 대해 항상 두 가지 경우가 생기기 때문에

내가 이제껏 풀어왔던 재귀함수와 달리 호출된 함수의 리턴값이 단일값이 아니라

이를 잘 처리해주는 게 중요하다.

 

문제 :

1. 주어진 숫자 배열로 만들 수 있는 경우의 수 찾기 => 순열

2. 중복 제거 및 1의 자리수가 0인 경우 제외

2. 소수판별

 

해결 방법:

1. . 주어진 숫자 배열로 만들 수 있는 경우의 수 찾기 => 순열

숫자 배열로 만들 수 있는 숫자의 자릿수가 정해져 있지 않기 때문에 

n개의 배열이 주어졌다면 nP1 + nP2 + nP3 ... nPn으로 모든 자릿수의 경우를 구한다. 

//nP1 + nP2 + nP3 ... nPn
let result = [];
for(let i = 1; i <= numbers.length; i++ ){
	result.push(...getPermutations(numbers.split(''), i).map((v) => v.join("")))
}

 

2. 중복 제거 및 1의 자리수가 0인 경우 제외한다. 

Set을 사용하면 간편하게 중복을 제거할 수 있다. 

let set = [...new Set(result.filter((value) => value[0] != '0'))];

 

 

3. 소수판별

마지막으로 소수찾기인데 소수찾는 방법은 매우 다양한데 우선은 1, 2는 각각 확인해주고 해당 숫자의 절반 이하의 숫자들의 배수로 나누어떨어지는지 확인했다. 

 function findPrime(numbers) {
      let len = numbers.length;
      
      let answers = []
      
      //소수판별 배열
      for(let i = 0; i < len; i++){
        answers.push(true)
      }
      
      for (let i = 0; i < numbers.length; i++) {
      
        if (numbers[i] * 1 === 1) {
        
          answers[i] = false;
          
        }else if (numbers[i] * 1 === 2){
        
          answers[i] = true;
          
        }else{
          for(let j = 2; j <= numbers[i]/2; j++ ){
          
            if(numbers[i] % j === 0){
              answers[i] = false;
            }
            
          }
        }
      }// for
      return answers;
    }

 

코드가 너무 길어져버렸다. 

내일 좀 더 다듬어보는 걸로!

 

function solution(numbers) {

    const getPermutations = function (arr, selectNumber) {
      const results = [];
      if (selectNumber === 1) {
        return arr.map((value) => [value]);
      } 
      arr.forEach((fixed, index, origin) => {
        const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; 
        const permutations = getPermutations(rest, selectNumber - 1); 
        const attached = permutations.map((permutation) => [fixed, ...permutation]); 

        results.push(...attached); 
      });
      return results; // 결과 담긴 results return
    };

    let result = [];
    for(let i = 1; i <= numbers.length; i++ ){
        result.push(...getPermutations(numbers.split(''), i).map((v) => v.join("")))
    }

    let set = [...new Set(result.filter((value) => value[0] != '0'))];
    console.log(set);

    function find(numbers) {
      let len = numbers.length;
     
      let answers = []
      for(let i = 0; i < len; i++){
        answers.push(true)
      }
      
      for (let i = 0; i < numbers.length; i++) {
        if (numbers[i] * 1 === 1) {
          answers[i] = false;
        }else if (numbers[i] * 1 === 2){
          answers[i] = true;
        }else{
          for(let j = 2; j <= numbers[i]/2; j++ ){
            if(numbers[i] % j === 0){
              answers[i] = false;
            }
          }
        }
      }// for
      return answers;
    }
    
    let answer = find(set);
    let a = answer.filter((value, i)=> (value === true))

    return a.length;
}