[Programmers] level2 - 소수 찾기
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
풀이
python itertools의 permutations를 사용하면 빠르게 풀 수 있다.
흐름은 알겠는데 깨끗하게 작성하지를 못했다.
문자열로 입력받은 numbers를 list()를 사용해 한 글자씩 분리 시킨 리스트를 만든다. 문자열의 길이만큼 순열을 생성하면 종이 조각으로 만들 수 있는 모든 숫자 조합이 만들어진다. 조합 튜플들을 하나의 문자열로 묶고 int() 메서드로 정수화 시키면 0으로 시작하는 숫자들이 정리된다.
set()으로 중복을 제거하고 정리된 리스트의 원소들을 isPrime() 메서드로 소수인지 판별하여 최종적으로 그 갯수를 리턴했다.
from itertools import permutations def solution(numbers): numbers = list(numbers) num = [] for i in range(1, len(numbers)+1): num.append(permutations(numbers,i)) res = [] for n in num: for tups in n: res.append(int(''.join(tups))) res = list(set(res)) count = 0 for r in res: if isPrime(r): count+=1 return count def isPrime(n): if n<2: return False for i in range(2,int(n**0.5)+1): if n%i == 0: return False return True | cs |
map을 중첩해서 사용한다는 생각을 못해서 코드가 길어진 것 같다.
다른 사람이 푼 멋진 풀이법
from itertools import permutations def solution(numbers): a=set() for i in range(1,len(numbers)+1): a |= set(map(int,map(''.join,permutations(list(numbers),i)))) 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) | cs |
permutations를 사용하고 전체적인 흐름은 똑같은데 나는 set을 활용할 줄 몰라서 list로 비효율적으로 풀었고 이 풀이는 set을 최대한으로 활용한 멋진 풀이이다.
에라토스테네스의 체 또한 set을 사용해 간단하게 풀이했다.
나도 에라토스테네스의 체를 사용하려 했으나, 나는 중복을 제거한 각 숫자들에 대해 체를 만들고, 소수인지 판별하고 하다보니 당연하게도 시간초과가 발생했다.
No comments: