문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42839
풀이 방법
우선은 주어진 numbers에 대해 조합을 구해야 하는데, itertools를 사용하거나 직접 구하거나 하는 2가지 방법이 있다. 이전에는 직접 구현할 줄 알아야 한다고 생각해서 매번 직접 구했으나 이번에는 itertools도 사용해보기로 했다.
그리고 나서 각 조합에 대해 소수 여부를 판별해야 하는데 현재 모든 조합은 string으로 되어 있으므로 int로 변환해주면 '11과 011은 같은 숫자로 취급합니다.' 라는 부분을 처리할 수 있다. (int('11') == 11; int('011') == 11)
소수를 판별할 때 DP 방식을 사용할지 잠깐 고민했는데, 조합 리스트의 최솟값과 최댓값 사이의 모든 값에 대해 함수를 돌리는 것이 효율적이지 않을 것이라고 생각했다. 그런데 지금 생각해보니 이 방식이 더 효율적인 것 같네..?
아무튼 각 숫자(조합)에 대해 1 이하일 경우 바로 리턴하고 (소수는 1보다 큰 자연수여야 함) 1과 자기 자신 외의 숫자로 나누어진다면 리턴하는 식으로 해서 조건에 맞는 숫자만 answer에 카운트해주는 식으로 풀었다.
코드
- itertools 라이브러리를 사용한 풀이
from itertools import permutations
def solution(numbers):
answer_set = set()
perms = []
# 모든 길이의 조합을 구함
for length in range(1, len(numbers) + 1):
# permutation 객체를 처리하기 위해 list로 변환한 다음에 extend
perms.extend(list(permutations(numbers, length)))
for perm in perms:
check = int(''.join(perm))
flag = True
# 숫자가 0/1인 경우 처리
if 1 >= check:
flag = False
else:
# 소수 판별
for num in range(2, check):
if check % num == 0:
flag = False
break
if flag:
answer_set.add(check)
return len(answer_set)
print(solution("011"))
- 직접 조합을 구하는 풀이
def check_prime(num):
"""
소수 판별 함수
"""
if num <= 1:
return False
for n in range(2, num):
if num % n == 0:
return False
return True
def solution(numbers):
def dfs(now, remaining):
"""
조합을 구하는 함수
"""
nonlocal perms
if now:
perms.add(int(now))
for i in range(len(remaining)):
dfs(now + remaining[i], remaining[:i] + remaining[i + 1:])
answer = 0
perms = set()
dfs('', list(numbers))
for perm in perms:
# 소수일 경우 카운트
if check_prime(perm):
answer += 1
return answer
print(solution("011"))
