프로그래머스 - Lv.2 소수찾기 (백트래킹) JS

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

이 문제도 어제 포스팅한 문제와 같은 백트래킹 로직으로 풀이했다.

2023.10.04 - [개발/algorithm] - 프로그래머스 - Lv.2 모음사전(백트래킹) JS

어제 문제풀이와 다른 점이 있다면, 이 문제 풀이는 중복되는 연산을 피하기 위해 노력했다는 정도.

(이전 '모음 사전' 문제는 중복을 고려할 필요가 없었음)

 

문제 풀이 로직은 다음과 같다.

먼저 주어진 수를 쪼개어 배열로 만든 뒤,

해당 배열을 백트래킹 로직을 사용하여 만들 수 있는 모든 경우를 만들도록 했다.

이때 연산을 효율적으로 하기 위해 visited 배열 / table 객체를 선언했는데,

visited 배열은 주어진 수를 중복으로 사용하지 않기 위한 용도며,

table 객체는 백트래킹에서 생성된 값이 중복되어 처리되지 않기 위한 용도로 활용했다.

그리고 두 조건에서 중복되지 않은 수의 경우, 소수 검증 함수를 거쳐 소수일 경우 결괏값에 추가된다.

 

소스 코드

// 소수검증 함수
const verify = (n) => {
  if(n < 2) return false
  for(let i = 2 ; i <= Math.sqrt(n) ; i ++)
    if(n % i === 0) return false
  
  return true
}

function solution(numbers) {
  const arr = numbers.split('').sort((a,b)=> a-b)
  const table = {}
  let storage = ''
  let result = 0
  const visited = Array.from({length : arr.length}, ()=> false)

  const backTracking = () => {
    if(storage.length === arr.length) return
    else {
      for(let i = 0 ; i < arr.length ; i ++) {
        storage += arr[i]
        
        if(!visited[i]) {
          visited[i] = true
          // 중복되지 않은 수만 소수 함수 검증을 거침
          if(!table[+storage]) {
            table[+storage] = true
            // 소수인 경우 결괏값 추가
            verify(+storage) && result ++
          }
          backTracking()
          visited[i] = false
        }
        storage = storage.slice(0, storage.length - 1)
      }
    }
  }

  backTracking()
  return result
}