두가지 풀이법이 있습니다. 첫번째는 일반적인 Greedy 풀이법이고 두번째는 에라토스테네스의 체를 이용한 풀이법입니다. 전공시간에 배운 적 있었는데 여기서 보니 반가웠습니다..ㅎ
첫번째 풀이는 특별한 점이 없으니 코드만 적어두고 두번째 풀이에 대해 살펴보겠습니다.
[첫번째 풀이]
from itertools import permutations
import math
def is_prime(number):
if number == 1 or math.sqrt(number) == int(math.sqrt(number)):
return False
flag = True
for d in range(2, int(math.sqrt(number)) + 1):
if number % d == 0:
flag = False
break
if flag:
return True
else:
return False
def solution(numbers):
answer = 0
for len_digit in range(1, len(numbers) + 1):
list_permutation = list(set(permutations(numbers, len_digit)))
for permutation in list_permutation:
if permutation[0] == '0':
continue
else:
# 소수인지 판단
if is_prime(int(''.join(permutation))):
answer += 1
return answer
|= 연산 이 연산은 집합(set)에서 유용하게 쓸 수 있습니다. '|'는 set의 관점에서 합집합 연산이며, '|='로 쓰게 되면 왼쪽 집합이 두 개의 합집합으로 새로 정의되게 됩니다. 따라서 왼쪽 집합에 오른쪽 집합의 원소를 추가하고 싶을 때 활용할 수 있습니다.
set 안에 range 처음에는 for문으로 원소를 하나씩 추가해줬습니다. 하지만 range()를 활용하게 되면 for문을 쓰지 않고 한번에 여러 원소를 추가 가능합니다.
list의 여러 원소들의 값을 동시에 같은 값으로 변경하고 싶을 때 이때 주의점은 좌변 list는 인덱싱 형태로 접근해야하며, 우변의 값은 하나의 값이 아닌 좌변의 list와 크기가 같은 배열로 값이 주어져야 합니다. (처음에는 우변을 'False'로 하여 에러가 났습니다.)
코드는 아래와 같습니다.
from itertools import permutations
import math
def solution(numbers):
answer = 0
set_number = set()
for i in range(1, len(numbers) + 1):
set_number |= set(map(int, map(''.join, permutations(numbers, i))))
set_number -= {0, 1}
max_number = max(set_number)
list_prime = [True] * (max_number + 1)
for prime in range(2, int(math.sqrt(max_number)) + 1):
if list_prime[prime]:
set_number -= set(range(prime * 2, max_number + 1, prime))
list_prime[prime * 2:max_number + 1:prime] = [False] * len(list_prime[prime * 2:max_number + 1:prime])
answer = len(set_number)
return answer
