https://school.programmers.co.kr/learn/courses/30/lessons/42839
문제 파악
numbers라는 배열에 0~9 숫자가 띄어쓰기 없이 이어져 문자열로 주어져 있다.
이를 하나씩 순서를 바꿔 조합했을 때 만들 수 있는 '소수의 개수'를 return 해주면 된다.
예시 1
numbers "17" 이 주어졌다면
소수 7,17,71 을 만들 수 있기에 return 3
numbers "011" 가 주어졌다면
소수 11,101 를 만들 수 있기에 return 2
해결 아이디어
어떻게 풀 수 있을까?
문제의 numbers 길이는 1 이상 7 이하.
최대 경우의 수는 대략 7! + 6! + … + 1! 수준이라 완전탐색(브루트포스)로 충분하다.
오케이 모든 자리에 수들을 조합해볼건데, 그럼 소수판별은 어떻게?
에라토스테네스의 체 방식도 있지만, 이번 문제처럼 여러 후보를 검사하지만 상한이 10⁷ 미만인 상황에선 √n까지만 나눠보는 방식이 간단하고 빠르다.
def is_prime(n):
if n < 2:
return False
for i in range(2, n//2+1):
if n % i == 0:
return False
return True 해답 및 풀이
from itertools import permutations
def is_prime(n):
# 2 미만은 소수 아님
if n < 2:
return False
# √n까지만 나눠본다
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def solution(numbers): # 메인 함수
cand = set() # 중복을 없애기 위해 set(집합) 사용
for k in range(1, len(numbers) + 1): # 1자리부터 전체 자리까지 순열 생성
for p in permutations(numbers, k): # 예: numbers='17' → ('1',), ('7',), ('1','7'), ('7','1')
cand.add(int(''.join(p))) # 튜플을 문자열로 합치고 int로 변환 → 숫자로 저장
return sum(is_prime(x) for x in cand) # cand의 모든 숫자에 대해 is_prime이 True면 1로 더함 → 총 소수 개수 반환
itertools.permutations() 란?
파이썬 표준 라이브러리 itertools 안에 있는 함수로,
순열(permutation), 즉 순서를 고려한 모든 경우의 수를 만들어준다.
기본 사용법
from itertools import permutations
permutations(iterable, r=None)iterable : 리스트, 문자열, 튜플 등 반복 가능한 객체
r : 뽑을 원소 개수 (생략하면 전체 길이)
사용 예시
from itertools import permutations
nums = ['1', '2', '3']
# 1) 전체 길이(3개)로 순열 생성
print(list(permutations(nums)))
# [('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'),
# ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]
# 2) 2개만 뽑는 순열
print(list(permutations(nums, 2)))
# [('1', '2'), ('1', '3'), ('2', '1'),
# ('2', '3'), ('3', '1'), ('3', '2')](iterable)P(r) 로 이해하자.
permutations(iterable,r) => iterable 중 r개 순서 고려해서 선택
이때 결과는 튜플형태로 나오니, 위 코드에선
문자열로 합치기 위해 ''.join(p) 를 해줬고
int() 로 묶어 앞에 0을 떼어줬고, 집합 자료형에 add에 해주어 중복을 제거해주었다.
