[Algorithm] 프로그래머스 - 소수 찾기 (브루트포스 - Brute Force)

 

 

 

프로그래머스 문제입니다.

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요

 

---

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

---

입출력 

---

입출력 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

 

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

---

문제풀이

function solution(numbers) {
    var answer = 0
    
    // (1)
    const permutation = recursive(numbers.split(''))
    const filtered =  [...new Set(permutation)]
    // (2)
    const max = Math.max(...filtered)
    const eNet = eNetFilter(max)
  
    // (3)
    filtered.forEach(filtered_num => {
        if (eNet[filtered_num] === true) answer++
    })
        
    // (4) get eratosthenes net
    function eNetFilter(max) {
        let net = new Array(max + 1).fill(true)
        net[0] = false
        net[1] = false
        for (let i = 2; i < max + 1; i++) {
            if (net[i] === true) {
                for (var j = i+i;  j < max + 1; j+=i) net[j] = false
            }
        }
        return net
    }
    
    // (5) get all possible strings -> permutation
    function recursive (arr, prefix) {
       let _prefix = prefix || ''
       return arr.reduce((acc, cur, idx) => {
         acc.push(Number(_prefix + cur))
         const remainList = [...arr]
         remainList.splice(idx, 1)
         const remain = recursive(remainList, _prefix + cur)
         acc.push(...remain)
         return acc
       }, [])
    }
    
   return answer
}

 

idea: permutation을 구하기 위해 recursive (재귀 함수)를 사용하고, 에라토스테네스 체를 사용해서 prime의 여부를 가립니다.

1.  permutation (순열)을 통해 모든 경우의 수 리스트를 구하고, array -> set -> array 를 통해서 중복된 항목들을 걸러냅니다.

2. set으로 filter된 리스트에서 max 값을 통해 에라토스테네스의 체를 만듭니다.

3. 리스트의 아이템마다 소수(prime) 여부를 확인한 후 answer 값을 증가시킵니다.

4. max 정수를 받아 max까지의 에라토스테네스의 체 배열을 만들어 리턴합니다.

5. 순열을 통해 모든 경우의 수를 고려하기 위해 재귀함수를 사용합니다.

   첫번째 인덱스부터 요소를 하나씩 빼서(cur) 순열 리스트 (acc)에 넣고 픽스 (_prefix + cur) 시킵니다.

   고정된 리스트의 이외를 인자로 하여 다시 recursive 함수를 콜합니다.

그리고 return!