[프로그래머스] 소수 찾기

---

문제설명

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

코딩테스트 연습 - 소수 찾기

사고과정

• DFS로 완전탐색 하면서 특정 수가 소수인지 판별하는 알고리즘을 사용하면 된다.
• 어차피 수는 0~9 사이로 주어진다고 했으니 주어지는 문자열 즉, 숫자가 붙어있는 문자열에 "109"라면 1,0,9 인지 10, 9 인지 따로 처리해주지 않아도되서 편했다. 무조건 1,0,0를 뜻하니깐!
• 처음에 완전탐색할 때, 부분집합을 구하는 것인가 했지만, 순서가 다른것도 다른 것으로 간주하는 중복을 허용하지 않는 순열임을 눈치챘다. 그리고 난 후 잘 생각해보니 주어진 문자열 길이를 1부터 loop를 돌면서 완전탐색을 수행하면 되었다. 어차피 문제에서 주어진 수의 범위도 크지 않기에 시간 복잡도 내에 해결할 수 있다고 생각했다.
• 그리고 01, 1 과 같은 것은 동일하게 1이기 때문에 중복을 제거하도록 하기 위해 완전탐색 한 후 int 형으로 변환 후 집합 자료구조에 넣어주었다. 그리고 완전탐색이 종료된 후 집합 자료구조를 Loop 돌면서 정의한 소수 판별 알고리즘에 넣어주었다. 이 때, 소수 판별 알고리즘은 math 라이브러리를 활용해 시간 복잡도를 $\log{X^{\frac{1}{2}}}$를 개선할 수 있도록 했다.

풀이

import math

def is_prime_number(x):
    if x == 0 or x == 1:
        return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

def solution(numbers):
    result = set()
    
    for length in range(1, len(numbers)+1):
        res = [0] * length
        visited = [0] * len(numbers)

        def dfs(L):
            if L == length:
                value = ''.join(res)
                result.add(int(value))
            else:
                for i in range(len(numbers)):
                    if visited[i] == 0:
                        visited[i] = 1
                        res[L] = numbers[i]
                        dfs(L+1)
                        visited[i] = 0
        dfs(0)
    
    answer = 0
    for x in result:
        if is_prime_number(x):
            answer += 1
    return answer