문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다."013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예 입출력 예 설명 예제 #1[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다. 11과 011은 같은 숫자로 취급합니다.
코드
from itertools import permutations
def solution(numbers):
# 숫자 리스트
li = list(numbers)
num_li = list(map(int, li)) # 문자열로 입력 받은 숫자를 정수 리스트로 변환
all_num = set() # 중복 방지
# 모든 가능한 숫자 조합 생성
for r in range(1, len(num_li)+1):
perms = permutations(num_li, r) # 1자릿수부터 최대 자릿수까지
for p in perms:
number = int("".join(map(str,p)))
all_num.add(number) # 중복제거
# 소수 판별
primes = []
for i in all_num:
is_prime = True # 최초에는 소수라고 가정
if i < 2: # 2보다 작은 숫자는 소수가 아님
continue
for j in range(2,i): # 검증하려는 숫자를 2부터 자기 자신을 제외한 i-1까지 나누기
if i%j == 0: # 나누어떨어지면 소수가 아님
is_prime = False
break
if is_prime: # 소수라면 리스트에 추가
primes.append(i)
return len(primes)
개선점 및 회고
소수 판별 시 제곱근까지만 나누자.
소수를 판별할 때,
2부터 N-1 까지 전체를 나누면서 확인할 필요 없이
2부터 √N 까지만 나눠서 확인해도 된다.
[예시]
N = 36 일 때, 약수 쌍은 (1,36),(2,18),(3,12),(4,9),(6,6).
여기서 작은 약수들은 모두√36 = 6 이하임을 알 수 있다.
따라서 36의 소수 여부를 판별하기 위해 나누기를 할 때, √36 까지만 나눠줘도 된다는 것!
