[Programmers] 소수 찾기 / JavaScript

문제

---

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

코딩테스트 연습 - 소수 찾기

 

코드

---

function solution(numbers) {
  const arr = numbers.split("");
  const answer = new Set(); //정답(소수)을 넣을 set 선언
 
  getPermutation(arr, ""); //순열 함수 호출
 
  //완전탐색할 순열 함수
  function getPermutation(arr, fixed) {
    //매개변수 arr의 요소가 있을때까지만 반복 (사실상 이부분을 이해하는 것이 중요 -> 요소가 없다면 백트래킹이 적용되므로)
    if (arr.length > 0) {
      //arr의 각 요소에 대해
      for (let i = 0; i < arr.length; i++) {
        const newFixed = fixed + arr[i]; //기존의 고정값에 배열의 요소를 하나씩 붙이며 고정값을 늘려나감 -> 이렇게 늘려나가면서 arr.length > 0 일 때 까지 반복하는 것
        const copyArr = [...arr]; //백트래킹으로 다시 돌아오려면 arr원본이 필요하기 때문에 arr의 복사본으로 다음 진행
        copyArr.splice(i, 1); //기존 fixed에 newFixed로 붙여진 arr[i]는 제거하기 (이렇게 되면 copyArr에는 고정되지 않은 요소들이 남게됨)
 
        //새로운 고정값은 소수 판별 후 맞으면 정답 set에 add
        if (isPrime(parseInt(newFixed)) === true)
          answer.add(parseInt(newFixed));
 
        //재귀를 통해 배열의 요소가 없을 때까지 계속 고정값을 늘려가며 순열 구하기
        getPermutation(copyArr, newFixed);
      }
    }
  }
 
  //소수 판별 함수
  function isPrime(num) {
    if (num < 2) return false; //2보다 작은 수 중에 소수는 없다
    //2부터 num-1의 수 중에서 num으로 나누어떨어지는 수가 있다면 소수가 아니다
    for (let i = 2; i < num; i++) {
      if (num % i === 0) return false;
    }
    //그 외에는 true를 return
    return true;
  }
 
  return answer.size; //정답 set에 들어있는 소수들의 크기로 return
}

 

후기

---

• 결론부터 말하자면 이 문제는 내힘으로 풀진 못했고, 다른 분의 풀이를 봤지만 이해가 한 번에 되지않아 이틀에 걸쳐 이해를 하게됐다. 나름대로 순열을 이해하고 있다고 생각했는데, 이 문제를 풀면서 제대로 이해하고 있지 못한 내 상태를 알게됐고, 풀이를 보고도 제대로 이해가 안되는 내 자신이 너무 답답했다ㅜㅜ
• 연습장에 과정을 하나하나 손으로 써가며 복기해보니 비로소 이해하게 되었고, 내가 가장 이해가 안 갔던 부분이 백트래킹 부분이었다는 것을 알게 되었다.

• 

• 참고로, https://sumin-k.medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-javascript-%EC%99%84%EC%A0%84-%ED%83%90%EC%83%89-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-1fdcdca4f59b 풀이는 이블로그를 참고하였다.
• 위 그림에서 4)번째 과정이 이해가 안되는 부분이었는데, 직전 과정을 통해 copyArr=[]가 되어, 재귀함수의 매개변수로 빈 배열이 주어졌기 때문에 코드의 if (arr.length > 0) 부분에서 false가 발생하여 백트래킹이 적용되어 2)번째 과정으로 돌아가 i=0에서 i=1로 바뀐 for문이 진행되는 것이다.
• 그림의 왼쪽 상단 트리 구조는, 구조만 보면 이해는 갔으나 (빨간색이 fixed) 저 트리 구조만 보고 코드를 이해하는 데는 한계가 있었다. 그래서 하나하나 과정을 써가며 트리 구조와 함께 이해하니 코드가 이해됐다.
• 생각보다 몇 줄 안되는 코드였지만 많은 것을 배운 문제였다.

---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀