Programmers - 소수 찾기(Python)
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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
import math
def check(n):
k = math.sqrt(n)
if n < 2:
return False
for i in range(2, int(k)+1):
if n % i == 0:
return False
return True
def solution(numbers):
answer = []
for k in range(1, len(numbers)+1):
perlist = list(map(''.join, permutations(list(numbers), k)))
for i in list(set(perlist)):
if check(int(i)):
answer.append(int(i))
answer = len(set(answer))
return answer
numbers = "17"
print(solution(numbers)) # 결과 예 : 3
from itertools import permutations
import math
def check(n):
k = math.sqrt(n)
if n < 2:
return False
for i in range(2, int(k)+1):
if n % i == 0:
return False
return True
def solution(numbers):
answer = []
for k in range(1, len(numbers)+1):
perlist = list(map(''.join, permutations(list(numbers), k)))
for i in list(set(perlist)):
if check(int(i)):
answer.append(int(i))
answer = len(set(answer))
return answer
numbers = "17"
print(solution(numbers)) # 결과 예 : 3
풀이 과정
1) check라는 함수를 만들어서 소수를 판정한다. 여기서, math.sqrt를 사용하는 이유는 제곱수의 경우 소수가 아니기 때문에 이를 통해 판정한다.
2) permutations를 이용해서 모든 경우의 수를 만들고 판정한다. 단, 여기서 중복되는 수가 발생해서 set으로 미리 줄이고 하면 속도가 많이 빨라진다.
3) answer에 모든 소수를 집어넣고 길이를 출력하면 정답이 나온다.
📝 결과
😃 느낀점
- permutations가 있다는 것을 몰랐다. 이것을 알게 되었음에 감사를 느낀다.
👍 Irish의 모든 코드 보기
-> Irish Github
Author And Source
이 문제에 관하여(Programmers - 소수 찾기(Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@irish/Programmers-소수-찾기Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)