Brute force: 소수 찾기 [Lv2]
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
Solution
내 풀이
def isPrime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def DFS(num_list, ch, number, primes):
if all(ch):
if number not in primes and isPrime(number):
primes.append(number)
else:
if number not in primes and isPrime(number):
primes.append(number)
for i, v in enumerate(ch):
if v == 0:
ch[i] = 1
use = num_list[i]
primes = DFS(num_list, ch, int(str(number) + str(use)), primes)
ch[i] = 0
return primes
def solution(numbers):
size = len(numbers)
ch = [0] * size
res = DFS(numbers, ch, 0, [])
answer = len(res)
return answerDFS와 에라토스테네스의 체 사용.
numbers와 크기가 같은 리스트 ch를 만들어 모두 0으로 채운다.
numbers에서 사용한 숫자의 인덱스에 해당하는 ch의 값을 1로 만들어 숫자의 사용 유무를 구별한다.
DFS에서 all(ch)는 ch에 0이 존재하지 않으면 True 반환. 모든 숫자를 사용했을 때,all(ch) 조건문의 조건 만족.
DFS에서 number이 소수 집합인 primes에 존재하는지 확인 후, isPrime을 통해 소수인지를 판별. 소수라면 primes 집합에 추가.
ch의 값이 0인 인덱스에 해당하는 num_list값(초기 numbers에서 사용되지 않은 값)을 찾아 다음 DFS 호출.
DFS의 리턴값은 primes이다. 하의 DFS에서 primes에 한 번 담은 값들을 상위 DFS에도 사용하기 위함이다.
solution에서는 DFS의 리턴값의 길이를 다시 리턴한다.
결과
Best Code
from itertools import permutations
def solution(numbers):
a = set()
for i in range(len(numbers)):
a |= set(map(int, map("".join, permutations(list(numbers), 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)해당 숫자들로 만들수 있는 모든 수를 set에 담은 다음에 소수가 아닌 수를 빼는 형식으로 소수를 모두 구한다.
순열을 구할 수 있는 itertools.permutations 함수를 import한다.
set(map(int, map("".join, permutations(list(numbers), i + 1))))을 통해 numbers를 리스트로 만들어, 여기서 i+1개의 원소로 수열을 만든다음 join하여 리스트로 만든다. 각각의 원소를 int형으로 만든 후에 리스트를 set으로 만들어준다. 이를 a와 비교하여 a에 없는 값을 a에 넣어준다.
a에서 이제 소수가 아닌 수를 빼줘야 하는데, 0~1은 소수가 아니므로 이를 먼저 빼준다.
그 후에 for문을 통해 a에서 i*2 부터 a의 최댓값(max(a))까지의 i의 배수를 빼준다. i*2부터 빼는 이유는 i는 소수 아니면 i보다 작은 숫자의 배수로써 이미 빠졌기 때문이다.
for문에서 i의 범위가 2부터 int(max(a) ** 0.5 + 1)인 이유는 i가 max(a)를 넘지 않게 하기 위함이다.
결과
실행 시간을 보면 이 코드가 내가 짠 코드보다 worst인 경우의 실행시간이 짧은 것을 알 수 있다.
그도 그럴 것이 나는 소수의 중복을 in을 통해 걸렀고 이 코드는 set을 통해 걸렀기에 차이가 많이 난듯..
