문제
접근
완전 탐색 문제이다.
모든 조합을 확인해봐야 하는 것은 확실하다.
그렇다면 확인하는데 걸리는 시간을 줄이는 방향으로 접근해야 할 것 같다.
해당 조합으로 나올 수 있는 최대치까지 소수를 미리 찾아놓고, 해당 숫자의 index로 접근하는 식으로 구현한다면 소수인지 판별하는데 걸리는 시간은 O(1)으로 해결할 수 있다.
단점은 메모리는 많이 잡아 먹을 것이다.
모든 조합을 확인하는 방법은 재귀를 이용해 진행하는 것도 가능하며, 파이썬의 경우 permutations 을 이용하여 쉽게 연산이 가능하다.
여기서는 연습을 위해 재귀를 이용해 모든 조합을 직접 탐색하였다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
answer = set()
check = [0] * 7
def solution(numbers):
numList = list(numbers)
numList.sort(reverse=True)
maxNum = int(''.join(numList))
dp = [1] * (maxNum+1)
dp[0] = dp[1] = 0
for i in range(2, maxNum+1):
if dp[i] != 1:
continue
for j in range(i*2, maxNum+1, i):
dp[j] = 0
bf(dp, numList, 0, len(numList), '')
print(numList)
return len(answer)
def bf(dp, num, cnt, limit, nowStr):
if cnt == limit:
return
for i in range(limit):
if check[i] == 0:
check[i] = 1
nowStr += num[i]
nowInt = int(nowStr)
if dp[nowInt] == 1:
answer.add(int(nowStr))
bf(dp, num, cnt+1, limit, nowStr)
nowStr = nowStr[:-1]
check[i] = 0