[프로그래머스] 소수 찾기 (JavaScript) Level 2

알고리즘 문제풀이 [프로그래머스] 소수 찾기 (JavaScript) Level 2

프로그래머스 Level 2 - 소수 찾기

• 문제 분류: 완전탐색
• 문제 출처: 프로그래머스 Level 2 - 소수 찾기
• 라벨: Level 2, JavaScript

문제

• 입력: 문자열("013"은 0, 1, 3 숫자가 적힌 종이 조각이라는 의미)
• 출력: 종이 조각에 쓰여진 숫자를 조합해 만들 수 있는 소수가 몇개인지 리턴 = 숫자

풀이

• numbers 문자열을 split()으로 쪼개 배열(splitArr)로 만든다.
• 순열을 사용해 가능한 모든 경우의 수를 구한다.(getPermutations()) 순열을 사용하는 이유는 0과 1을 뽑는 것과 1과 0을 뽑는 것은 다르기 때문이다. (numbers의 숫자가 "011"이라면 이중에서 1개, 2개, 3개를 뽑아 조합가능한 모든 경우를 구한다.)
• 조합가능한 경우(ex.["0", "1"])를 join()으로 이어붙이고("01") 숫자로 바꾼다.(1이됨) 이를 배열(candiArr)에 추가한다.
• 조합가능한 경우가 담긴 배열(candiArr)을 Set(candiSet)으로 만들어 중복을 제거한다.
• Set(candiSet)에서 하나씩 꺼내며 소수인지 검사하고 소수인 경우 answer값을 증가시킨다.

풀이1 코드

function getPermutations(arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((v) => [v]);
  else {
    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;
}

// 소수인지 판별
function isPrime(num) {
  // 소수는 1과 자기 자신만으로만 나누어 떨어지는 수 임으로
  // num > i
  for (let i = 2; num > i; i++) {
    if (num % i === 0) {
      //이 부분에서 num이  다른 수로 나눠떨어진다면 소수가 아님
      return false;
    }
  }
  // 소수는 1보다 큰 정수임으로
  // 1보다 작으면 false를 리턴한다
  return num > 1;
}

function solution(numbers) {
  let answer = 0;

  const candiArr = [];

  const splitArr = numbers.split("");
  for (let i = 1; i < numbers.length + 1; i++) {
    candiArr.push(
      ...getPermutations(splitArr, i).map((v) => Number(v.join("")))
    );
  }

  const candiSet = new Set(candiArr);
  candiSet.forEach(function (v) {
    if (isPrime(v)) answer++;
  });

  return answer;
}

• 시간 복잡도: O(n^2)보다 클 것으로 예상

  • solution() 내부 for 반복문(numbers의 길이가 n이라고 가정할 때 n번 반복) 안에서 getPermutations() 내부 forEach문(최대 n번 반복)이 실행되므로

• 실행 시간이 오래 걸리는 것 같아서 개선하고 싶다.

References

• JavaScript로 순열과 조합 알고리즘 구현하기 순열 코드 출처

• 소수(Prime number) 판별법 [ JavaScript ] 소수 판별 코드 출처