https://programmers.co.kr/learn/courses/30/lessons/42839
문자열 형태로 주어지는 숫자로 만들 수 있는 모든 수에서 소수의 갯수를 찾는 문제이다. 이 문제를 두 개로 나누어보자.
1) 문자열 형태로 주어지는 숫자로 만들 수 있는 모든 수를 구하기.
2) 소수를 찾기.
먼저 1)번을 보자. 문자열 형태로 주어지는 숫자란, "17", "011" 등을 말한다. 만약 "17"이 주어졌다면 "1", "7"로 만들 수 있는 모든 수를 구해야 한다.
문자열 형태든 무슨 형태든 일단 헷갈리니까 1과 7을 가지고 모든 수를 구하는 방법을 생각해보자.
모든 수를 구한다는 것은 가능한 모든 경우의 수를 구한다는 것이다. 순열을 구하는 방식으로 가능한 모든 경우의 수를 구할 수 있겠다. (조합이 아님)
그리고 매개변수가 문자열 형태로 주어지므로, "17"을 "1"과 "7"로 만들기 위해서 간단히 문자열을 리스트로 감싸주자.
ex) list("17") --> ["1", "7"]
1)번 문제는 for문을 직접 돌며 재귀로 구할 수도 있고, itertools의 permutation을 이용해서 풀 수도 있다.
itertools 방식이 훨씬 깔끔하긴 하다.
2)번 소수를 찾는 문제에 대해 얘기해보자. 만약 작은 수부터 차례대로 소수를 구하는 문제였다면 소수 판별을 위해서 더 작은 소수로만 나눠보려고 했을 것이다.
하지만 이 문제에서는 "17"처럼 7보다 작은 소수인 2, 3, 5가 등장하지 않고 7이 제일 먼저 등장할 수도 있다.
그래서 자기보다 작은 소수로 나눠보는 방식으로 판별은 불가능하고(아니 복잡해지고), 1보다는 크고, 자신의 제곱근보다 같거나 작은 수로 나눠봐야 한다.
itertools를 사용하지 않은 코드
def dfs(n_list, checked, true_cnt, primes, selected):
if true_cnt > 0:
n = int("".join(selected))
if is_prime(n):
primes.add(n)
if true_cnt == len(n_list):
return
for idx, ch in enumerate(checked):
if not checked[idx]:
checked[idx] = True
selected.append(n_list[idx])
dfs(n_list, checked, true_cnt+1, primes, selected)
checked[idx] = False
selected.pop()
return primes
def solution(numbers):
n_list = list(numbers) # numbers의 길이를 알아내기 위해 리스트로 바꾼다.
checked = [False for _ in n_list]
return len(dfs(n_list, checked, 0, set(), []))
itertools를 사용한 코드
from itertools import permutations
def is_prime(n):
prime = True
if n < 2:
prime = False
for i in range(2, int(n ** 0.5)+1): # n의 0.5제곱 = 제곱근
if n % i == 0:
prime = False
return prime
def solution(numbers):
answer = set()
for i in range(1, len(numbers)+1):
for p in permutations(numbers, i):
n = int("".join(p))
if is_prime(n):
answer.add(n)
return len(answer)
