๐ ์์ ์ฐพ๊ธฐ
in Algorithm on Brute force, ์๋ผํ ์คํ
๋ค์ค์ ์ฒด
ํ๋ก๊ทธ๋๋จธ์ค Level2
[Class2] ์์ ์ฐพ๊ธฐ
๋ฌธ์ ์ค๋ช
ํ์๋ฆฌ ์ซ์๊ฐ ์ ํ ์ข ์ด ์กฐ๊ฐ์ด ํฉ์ด์ ธ์์ต๋๋ค. ํฉ์ด์ง ์ข ์ด ์กฐ๊ฐ์ ๋ถ์ฌ ์์๋ฅผ ๋ช ๊ฐ ๋ง๋ค ์ ์๋์ง ์์๋ด๋ ค ํฉ๋๋ค.
๊ฐ ์ข ์ด ์กฐ๊ฐ์ ์ ํ ์ซ์๊ฐ ์ ํ ๋ฌธ์์ด numbers๊ฐ ์ฃผ์ด์ก์ ๋, ์ข ์ด ์กฐ๊ฐ์ผ๋ก ๋ง๋ค ์ ์๋ ์์๊ฐ ๋ช ๊ฐ์ธ์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- numbers๋ ๊ธธ์ด 1 ์ด์ 7 ์ดํ์ธ ๋ฌธ์์ด์ ๋๋ค.
- numbers๋ 0~9๊น์ง ์ซ์๋ง์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- โ013โ์ 0, 1, 3 ์ซ์๊ฐ ์ ํ ์ข ์ด ์กฐ๊ฐ์ด ํฉ์ด์ ธ์๋ค๋ ์๋ฏธ์ ๋๋ค.
์ ์ถ๋ ฅ ์
|numbers|return| |โโ|โโ| |โ17โ|3| |โ011โ|2|
์ ์ถ๋ ฅ ์ ์ค๋ช
์์ #1
[1, 7]์ผ๋ก๋ ์์ [7, 17, 71]๋ฅผ ๋ง๋ค ์ ์์ต๋๋ค.
์์ #2
[0, 1, 1]์ผ๋ก๋ ์์ [11, 101]๋ฅผ ๋ง๋ค ์ ์์ต๋๋ค.
- 11๊ณผ 011์ ๊ฐ์ ์ซ์๋ก ์ทจ๊ธํฉ๋๋ค.
# ๐ ๊ฐ์ ธ๋ค ์ฐ๊ธฐ
๋ฌธ์ ๋ถ๋ฅ์ "์์ ํ์"์ด๋ผ๊ณ ์ฐ์ฌ ์์ด์ ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ฏธ ์๊ณ ๋ค์ด๊ฐ๋ค.
์ถ๊ฐ์ ์ธ ์กฐ๊ฑด์ด๋ผ๋ฉด ์์๋ฅผ ์ฐพ๋ ๋ฌธ์ ์ด๊ธฐ์ **์๋ผํ ์คํ
๋ค์ค์ ์ฒด** ๋ฅผ ์ฐ๋ฉด ๋๊ฒ ๋ค๊ณ ์๊ฐํ์๋ค.
# ๐ ๊ณผ์ ์ค๊ณ/๊ด๋ฆฌ
![แแ
งแซแแ
ณแธแแ
กแผ-59](https://user-images.githubusercontent.com/88064555/181423333-e85ac4fc-45ad-4835-ba71-19b5dc3a1d52.jpg)
๋ก์ง์ ์ง๋ค๋ณด๋ ์์ด์ด ํ์ํ์๋ค. ํ์ด์ฌ ๋ด์ฅ ๋ชจ๋์ธ permutation์ importํ์ฌ ์ฌ์ฉํ์๋ค.
# ๐จ๐ปโ๐ป CODE
```python
from itertools import permutations as p
MAX = 9999999
# ์์ ๊ฒ์ฆ ํจ์ - ์๋ผํ ์คํ
๋ค์ค์ ์ฒด
def is_prime(n):
sieve = [True]*(n+1)
m = int(n**0.5)
for i in range(2,m+1):
if sieve[i] == True:
for j in range(2*i,n+1,i):
sieve[j] = False
return sieve
prime = is_prime(MAX)
prime[0], prime[1] = False,False
def solution(numbers):
arr = list(map(int,numbers))
permu = []
for i in range(1,len(arr)+1):
permu.extend(list(p(arr,i)))
result = []
for i in range(len(permu)):
temp = ""
for j in range(len(permu[i])):
temp += str(permu[i][j])
result.append(int(temp))
result = set(result)
result = list(result)
count = 0
for i in range(len(result)):
if prime[result[i]] == True:
count += 1
return count
๊ณ ์์ ํ์ด
์ด ๋ถ์ ์ง์ ํ ํ์ดํ ๋์ธ๋ฏ โฆ
from itertools import permutations
def solution(n):
a = set()
for i in range(len(n)):
a |= set(map(int, map("".join, permutations(list(n), i + 1))))
a -= set(range(0, 2))
for i in range(2, int(max(a) ** 0.5) + 1):
a -= set(range(i * 2, max(a) + 1, i))
return len(a)