[프로그래머스_JS] 소수 찾기

문제

프로그래머스 소수 찾기 문제

input: 숫자로 이루어진 문자열

output: 숫자를 조합해서 만들 수 있는 소수 개수

 

네이스 풀이 분석

두 시간 안에 풀지 못해서 네이스 풀이를 분석했다. 코드 고마워요🙂

네이스 코드를 복사해서 vsc에서 디버깅하면서 공부했다.

 

function solution(numbers) {
    const answer = new Set();
    const visited = [];
    findPrime('', visited, answer, numbers); // N! * logN
    return answer.size;
  }
  
  function findPrime(prevSum, visited, answer, numbers) {
    if (visited.length === numbers.length)
      return 0;
  
    for (let i = 0; i < numbers.length; i++) {
      if (visited.find(v => v === i) !== undefined) // 방문했다면 continue (중복 제거)
        continue;
  
      const sum = prevSum + numbers[i];
  
      if (!answer.has(Number(sum)) && isPrime(Number(sum))) // logN
        answer.add(Number(sum));
  
      visited.push(i);
      findPrime(sum, visited, answer, numbers);
      visited.pop();
    }
  }
  
  function isPrime(number) {
    if (number === 2) return 1;
    if (number <= 1 || number % 2 === 0) return 0;
  
    for (let i = 3; i <= Math.sqrt(number); i += 2)
      if (number % i === 0) return 0;
  
    return 1;
  }

'123'을 예시로 트리를 그려보면 다음과 같다.

✱ 모든 경우의 수를 돌아야 하지만, 중복이 되면 안된다.

중복이 되지 않게 하기 위해서 방문했던 index를 visited라는 빈 배열을 만들어 넣어놓고, 돌 때마다 visited를 검사해서 방문했다면 continue해서 다음으로 넘어간다.

 

✱ 깊이로 들어가는 건 재귀, 중복 넘어가는 건 continue, 마지막 깊이에서 빠져나오는 건 return

✱ 재귀이기 때문에 흐름 순서는 DFS처럼 깊이우선탐색이다.

✱ visited.push(i) → 재귀 → visited.pop로 방문한 인덱스 관리

 

배운 것 정리

1. for(let i = 3; i <= Math.sqrt(number); i += 2) 여기서 루트를 사용한 이유는 약수의 절반만 돌기 위해서이다! +=2는 짝수는 건너뛰기 위해서!

2. Number('001')을 하면 앞의 0문자를 없앨 수 있다.

3. 코드의 흐름을 이해하자. 간단하게 정리 못하겠다ㅎㅎ