๋ง์์ ๊ธํ๊ฒ ๋จน์ผ๋ ์ฒ์ ์๋์์๋ ์ ํ๋ฆฌ์ง ์์๋ค.
์ฐจ๋ถํ๊ฒ ๊ฒฝ์ฐ์ ์๋ฅผ ํธ๋ฆฌ ํํ๋ก ๊ทธ๋ ค ๋ณธ ๊ฒ์ด ๋ฌธ์ ํ์ด์ ๋์์ด ๋๋ค.
๋ฌธ์
- ํ์๋ฆฌ ์ซ์๊ฐ ์ ํ ์ข ์ด ์กฐ๊ฐ์ด ์๋ค. ์ด๋ฅผ ๋ถ์ฌ ์์๋ฅผ ๋ช๊ฐ ๋ง๋ค ์ ์๋์ง ๋ฐํํ๋ผ.
์ ๋ ฅ๊ฐ
- 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)