๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿบ ๋งค์ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์†Œ์ˆ˜ ์ฐพ๊ธฐ 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)