Programmers. 소수 찾기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 소수 찾기

문제 풀이

풀이에 앞서 사전 작업이 조금 필요하다.

• numbers의 종이를 뽑아 숫자를 만드는 함수(Permutation)
• 만든 숫자가 소수인지 확인할 에라토스테네스의 체

위 2가지만 구현할 수 있으면 수월히 풀리는 문제였다. 에라토스테네스의 체의 범위는 numbers로 만들 수 있는 최대의 수 + 1로 잡으면 된다. 숫자는 1개부터 numbers의 길이만큼까지 뽑아서 만들 수 있는 수다.

python 코드

def solution(numbers):
    L = len(numbers)
    def permutation(r):
        buf = []
        visited = [0 for _ in range(L)]
        def gen(buf, sol):
            if len(buf) == r:
                s = int("".join(buf))
                if sieve[s] is True:
                    sieve[s] = None
                    sol += 1
                    return sol
            for i in range(L):
                if not visited[i]:
                    buf.append(numbers[i])
                    visited[i] = 1
                    sol = gen(buf, sol)
                    buf.pop()
                    visited[i] = 0
            return sol
        sol = gen(buf, 0)
        return sol
    N = int("".join(sorted(numbers, reverse=True)))
    sieve = [True] * (N + 1)
    sieve[0], sieve[1] = False, False
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] is True:
            for j in range(2 * i, N + 1, i):
                sieve[j] = False
    answer = 0
    for i in range(L + 1):
        answer += permutation(i)
    return answer