[programmers] 프로그래머스 소수 찾기 Level 2(Python)

(주)그렙

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

(Python)

(글쓴날 : 2020.06.19)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 소수 찾기 Level 2

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

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

---

2) 풀이 과정

* 시간 복잡도 : O(n!)

 

숫자들이 적힌 문자열이 주어지고 해당 숫자들로 만들 수 있는 수열 중 소수가 몇 개 인지 구하는 문제입니다.

 

저의 경우, DFS와 에라토스테네스의 체를 적용하였고, Python을 사용했습니다.

우선, 에라토스테네스의 체를 이용해 문제에서 가능한 숫자 범위의 소수들을 미리 구해놓은 뒤, 주어진 문자열에 DFS를 적용하여 순열을 구하였고, set()을 이용해 중복을 제거한 순열 중 소수의 개수를 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

def DFS(numbers, nums, stack, visit, isPrime):
    if stack:
        nums.add(int("".join(stack)))
            
    for i in range(len(numbers)):
        if not visit[i]:
            visit[i] = True
            stack.append(numbers[i])
            DFS(numbers, nums, stack, visit, isPrime)
            visit[i] = False
            stack.pop()
 
    
def solution(numbers):
    answer = 0
    
    isPrime = [False] + [False] + [True] * (9999997)
    
    for i in range(2, 9999997):
        if isPrime[i]:
            for j in range(i * 2, 9999997, i):
                isPrime[j] = False
        
    stack = []
    nums = set()
    visit = [False] * len(numbers)
    
    DFS(numbers, nums, stack, visit, isPrime)
    
    for num in nums:
        if isPrime[num]:
            answer += 1
            
    return answer

---