문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
내 풀이
from itertools import permutations def isprime(N): if N == 0 or N == 1: return False if N == 2 or N == 3: return True for i in range(2, int(N**0.5)+1): if N % i == 0: return False return True def solution(numbers): answer = 0 nums = set() for i in range(1, len(numbers)+1): nums |= set(map(''.join, permutations(numbers,i))) nums = set(map(int, nums)) for j in nums: if isprime(j): answer += 1 return answer
isprime 함수를 먼저 만들었다.
입력 N이 0 또는 1일 때는 소수가 아니므로 False를 반환하고, 2 또는 3이면 True를 반환한다.
그리고 for문에서 2부터 N^0.5 이하의 정수로 나눠 떨어지면 False를 반환한다.
N의 약수 중에서 자기자신을 제외하면 모두 N^0.5 이하이기 때문이다.
이 중에 해당하는 것이 없다면 True를 반환한다.
solution 함수를 살펴보자.
for문을 보면 numbers 리스트에서 i개의 원소의 순열을 만든다.
이를 join을 통해 연결한 뒤 set 담아서, 공집합으로 초기화 했던 nums과 합집한 연산을 한다.
이것을 int 함수를 거쳐 set에 다시 map을 하면 순열중에 제일 앞자리가 0이었던 요소들이 없어진다.
그리고 nums에 대한 for문에서 isprime 함수를 사용에 nums에 소수가 몇 개 있는지를 찾아 answer에 더한다.
정확성 테스트: ~6.19ms / 10.6MB
다른 풀이
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)
에라토스테네스의 체를 이용해 합성수를 제거한 방법을 사용했다.
첫 번째 for문에서 순열을 연결, int를 통해 앞자리 0을 제거, set으로 mapping해 중복을 제거하여 a를 만들었다.
a에서 {0, 1}을 차집합 연산을 해준 뒤에 에라토스테네스의 체를 적용한다.
2 이상 max(a)^0.5을 일의 자리까지 버림한 값 이하의 i에 대해 a와 i의 배수들을 차집합 연산 해준다.
그리고 결과적으로 남게 된 a의 길이를 반환한다.
효율성에서는 뛰어나진 않지만 소수를 구하는 데에 자주 쓰이는 에라토스테네스의 체 방법을 사용했기 때문에 풀이 해석을 해봤다.
