상세 컨텐츠

본문 제목

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

Problem Solving/programmers

by HelloMinchan 2020. 6. 19. 21:34

본문

(주)그렙

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

(Python)

(글쓴날 : 2020.06.19)

 


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

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


 

 

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


1) 문제

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

 

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

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 �

programmers.co.kr


2) 풀이 과정

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

 

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

 

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

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


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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(29999997):
        if isPrime[i]:
            for j in range(i * 29999997, 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

 

관련글 더보기

댓글 영역