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

·2021년 10월 14일
0

코테문제풀기

목록 보기
11/57

문제확인

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

문제풀이

const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((el) => [el]);
  // n개중에서 1개 선택할 때(nP1), 바로 모든 배열의 원소 return. 1개선택이므로 순서가 의미없음.

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    // 해당하는 fixed를 제외한 나머지 배열
    const permutations = getPermutations(rest, selectNumber - 1);
    // 나머지에 대해서 순열을 구한다.
    const attached = permutations.map((el) => [fixed, ...el]);
    //  돌아온 순열에 떼 놓은(fixed) 값 붙이기
    results.push(...attached);
    // 배열 spread syntax 로 모두다 push
  });

  return results; // 결과 담긴 results return
};

function isPrime(number) {
  if (number <= 1) return false;
  if (number <= 3) return true;
  if (number % 2 === 0) return false;

  for (let i = 3; i <= Math.sqrt(number); i += 2) {
    if (number % i === 0) return false;
  }
  return true;
}

function solution(numbers) {
  let answer = 0;
  let arrNumbers = numbers.split("");
  const resultSet = new Set();

  //i가 숫자 몇 개 고를거냐를 의미하니까 숫자의 개수만큼 돌아야 함
  for (let i = 1; i <= numbers.length; i++) {
    const resultOfPerm = getPermutations(arrNumbers, i).map((result) => Number(result.join('')));
    //Number()을 썻기 때문에 '011'로 Join됐다가 11로 바뀜
    //[1,7] -> resultOfPerm : [1,7]
    //[[1,7],[7,1]] -> resultOfPerm : [17,71]
    resultOfPerm.forEach((result) => { //중복 확인을 위한 부분
      if (!resultSet.has(result)) { //resultSet이 이 값을 가지고 있지 않다면
        resultSet.add(result); //resultSet에 추가 
        if(isPrime(result)) answer++;
        //중복으로 if문에 안걸린 인덱스들 빼고 모든 인덱스가 isprime()을 실행하게 됨
      }
    });
  }
  return answer;
}

0개의 댓글