프로그래머스 - 소수 찾기

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제요약

1. 숫자로 이루어진 문자열 numbers의 인자들로 만들 수 있는 숫자 중 소수의 개수를 구하라

풀이요약

1. 주어진 문자열로 만들 수 있는 숫자 조합을 모두 구해 set에 담는다.
2. set에 담긴 최댓값을 기준으로 에라토스테네스의 체를 구현해 set안의 수가 소수인지 판별한다.

코드

# 소수 판별 함수
def che(combi):
	# 문자열로 변환한 숫자 중 가장 큰 수를 기준으로
    m = max(combi)

    v = [0] * (m + 1)
    # 에라토스테네스의 체 구현
    for i in range(2, int(m ** 0.5) + 1):
    	# 이 때, v[i]가 0이라면 소수다!
        if not v[i]:
            for j in range(i * 2, m + 1, i):
                v[j] = 1
    value = 0
    for i in combi:
    	# i가 0이거나 1이면 소수가 아님
        if i < 2:
            continue
        # v[i]가 0면 소수
        if not v[i]:
            value += 1

    return value


def dfs(num, s):
    global combi
    # 만들어진 수는 set에 담는다
    combi.add(int(num))
    # s가 빈 문자열이면 멈춤
    if not s:
        return
    for i in range(len(s)):
        dfs(num + s[i], s[:i] + s[i + 1:])


def solution(numbers):
    global combi

    combi = set()
	# 일단 숫자를 만들고
    for i in range(len(numbers)):
        if numbers[i] != "0":
            dfs(numbers[i], numbers[:i] + numbers[i + 1:])
	# 소수가 몇 개인지 return
    return che(combi)