프로그래머스 - 소수 찾기 level 2

마음을 급하게 먹으니 처음 시도에서는 잘 풀리지 않았다.

차분하게 경우의 수를 트리 형태로 그려 본 것이 문제풀이에 도움이 됐다.

 

문제

• 한자리 숫자가 적힌 종이 조각이 있다. 이를 붙여 소수를 몇개 만들 수 있는지 반환하라.

 

입력값

• numbers: 0-9사이의 숫자로 구성된 문자열.
• 0 < numbers.length <= 7
• "101" 은 숫자 0 조각이 1개, 숫자 1 조각이 2개. 총 3조각이 있다는 뜻. 

 

출력값

• 만들 수 있는 소수의 갯수를 정수로 반환.

 

문제풀이

1. 우선 소수들을 미리 구했다. 그리고 집합에 넣어두어 O(1)시간 안에 소수 체크를 할 수 있도록 했다. 제한사항을 통해 입력값으로 들어올 수 있는 가장 큰 숫자를 유추할 수 있다. 0-9사이의 숫자로 구성된 문자열의 길이가 최대 7이 될 수 있으므로 가능한 가장 큰 숫자는 9999999이다. 그리고 소수는 에라스토테네스의 체 방식으로 구했다.

2. 백트래킹으로 가능한 숫자 조합을 구했다. nPn이므로 n!만큼의 조합이있다. (모두 서로 다른 숫자라고 가정했을 때) 

 

const MAX = 9999999
const primes = new Set(Array.from(Array(MAX), (_, i) => i+2))
for (let x = 2; x * x <= MAX; x++) {
    for(let n = 2; x * n < MAX; n++) {
        primes.delete(x * n)
    }
}

function solution(numbers) {
    const ans = new Set()
    const generate = (prefix, seen) => {
        for (let i = 0; i < numbers.length; i++) {
            if (!seen.has(i)) {
                const x = prefix + numbers[i]
                if (primes.has(x*1)) {
                    ans.add(x*1)
                }
                seen.add(i)
                generate(x, seen)
                seen.delete(i)
            }
        }
    }
    generate("", new Set())
    return ans.size
}

시간복잡도: O(N!)

공간복잡도: O(N)