문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한 사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
| numbers | return |
|---|---|
"17" | 3 |
"011" | 2 |
풀이
from itertools import permutations
from math import sqrt
def is_prime_number(number):
if number < 2:
return False
for div in range(2, int(sqrt(number)) + 1):
if not number % div:
return False
return True
def solution(numbers):
prime_number_table = set()
count = 0
for r in range(1, len(numbers) + 1):
result = map(''.join, permutations(numbers, r))
prime_number_table |= set(map(int, result))
for number in prime_number_table:
if is_prime_number(number):
count += 1
return count해결 과정
수들의 조합? 그렇다면 조합이나 순열 중 하나 아닐까?
주어진 numbers 안에 있는 수들을 조합하여 만들어진 수들 중에서 소수인 것만 판별하는 문제다.
이 말은 결국 numbers를 조합하라는 뜻인데, 이는 조합이나 순열 중 하나를 바로 연상시킬 수 있다.
다만, 만들어지는 수는 순서에 따라 그 값이 달라지기 때문에 순서가 있는 순열이 이번 문제에서 사용할 수 있을 것이라 생각했다.
from itertools import permutations그래서 itertools의 permutations를 불러와 사용하기로 했다.
한자릿수부터 종이조각의 갯수까지 조합이 가능하다.
일단 기본적으로 numbers는 현재 있는 종이 조각을 이어붙인 것이다. 즉, 선택할 수 있는 종이 조각은 최소 한 개부터 많게는 전체 다라는 뜻이다.
그러므로 순열을 만들 때 r은 1부터 len(numbers)까지 줘야 한다.
중복 제거
다만, permutations는 순열로 만들 수 있는 것을 모두 반환하지만 같은 값이 있어도 포함하여 반환한다. 같은 값을 가진 종이 조각이라고 하더라도 서로 다른 종이 조각으로 보는 것이다.
그래서 결과의 중복을 막기 위해 set으로 중복을 제거해주는 것이 좋다. 물론 그 전에 결과값들을 int를 통해 정수로 바꿔주면 더욱 좋다.
중복을 제거했다면 이후, 이전까지 구한 결과와 방금 구한 결과를 합집합을 하여 갱신한다. 파이썬의 set은 합집합 시 중복된 값은 하나만 넣는다는 특징이 있다.
소수 판별
그럼 set(result)에서 값을 하나씩 가져와 해당 수가 소수인지 판별한다.
소수라고 판별되었다면 count를 1 증가시킨다.
마무리
모든 수에 대한 검사가 끝났다면 count를 반환하여 문제를 해결하면 된다.
다른 사람의 풀이
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)우선, permutations를 통해 모든 경우를 구하는 것은 나와 동일하다. 이후, 해당 값에서 0과 1을 제거한다.
나는 해당 범위 내에서 나누어지는 것이 있다면 바로 False를 return하도록 했지만 이 풀이에서는 해당 값을 제외한 해당 값의 배수들을 전부 제거한다. 어차피 2는 소수이므로, 2를 제외한 2로 나누어지는 2의 배수들은 모두 소수가 아니기 때문이다.
그렇게 제거한 집합의 남은 요소 값을 반환한다.
