[ 자바스크립트(JavaScript) ] 프로그래머스 level2 - 소수 찾기

📍 프로그래머스 2단계 - 소수 찾기

문제 보기

---

카테고리가 완전 탐색으로 나와있지만, 재귀 중에서도 중복을 허용하지 않는 순열을 이용해서 풀었다.(부분집합, 순열, 조합을 구하는 방법은 다음 글을 참고해주세요.) 로직을 작성하기 이전에 최대 numbers의 길이가 7이면 순열을 구하는 최악의 경우의 수는 9999999!라고 생각해서 시간 초과가 나는 거 아니야..?라는 생각을 했는데, 0부터 9999999를 탐색하는 게 아니라 numbers의 length를 돌며 순열을 구하는 로직이기 때문에 9999999!가 아니라 7!인것을 깨달았다.

 

문제를 풀며 주의할 점은, 11과 011은 같은 숫자로 취급합니다.라는 조건을 미루어 보아 중복된 값은 제거해야 하는데, 처음에 check배열(const check = Array.from({ length: 9999999 }, () => false))을 통해 중복된 값이 있으면 return하는 코드를 작성했으나, 하단 사진처럼 실행시간이 너무 오래 걸려 다른 방법을 모색했고 결론적으로 set을 이용하여 중복을 제거하니 실행시간이 현저히 빨라졌다.

 

소수를 구별하는 방법은 여러 가지가 있지만 반복문의 범위를 제곱근 + 1까지만 설정하면 더욱 빠르게 찾을 수 있다.(관련 글 보러 가기)

728x90

 

function solution(numbers) {
  const n = numbers.length;
  const set = new Set();

  for (let m = 1; m <= n; m += 1) {
    let visited = Array.from({ length: n }, () => 0);
    let temp = Array.from({ length: m }, () => 0);
    DFS(0, m, visited, temp);
  }

  function DFS(L, m, visited, temp) {
    if (L === m) {
      const number = Number(temp.join(""));
      const isPrimeNumber = isPrime(number);
      if (isPrimeNumber) set.add(number);
    } else {
      for (let i = 0; i < n; i += 1) {
        if (!visited[i]) {
          visited[i] = 1;
          temp[L] = numbers[i];
          DFS(L + 1, m, visited, temp);
          visited[i] = 0;
        }
      }
    }
  }

  return set.size;
}

function isPrime(n) {
  if (n === 0 || n === 1) return false;
  let flag = true;

  for (let i = 2; i <= Math.floor(n / 2) + 1; i += 1) {
    if (!flag) return false;
    if (n % i === 0) flag = false;
  }
  return true;
}