0%

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

작성일 Edited on In Disqus:

프로그래머스 - 연습 문제

Code (Python)

  • 완전탐색(Brute-Force)
  • itertools 없었으면 절대 못 풀었을 문제다. 그저 갓이썬…
  • itertools.permutation로 모든 숫자의 조합을 구해 리스트에 저장.
  • 숫자 조합 리스트의 최대값까지의 소수를 찾는다. 소수는 에라토스테네스의 체를 활용해서 찾으면 된다.
  • 소수 리스트와 숫자 조합 리스트의 합집합을 구하고 길이를 리턴한다.
  • 다음에는 itertools 없이 풀어봐야겠다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import itertools

def sieve(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return num

def solution(numbers):
    numbers_list = []
    for i in range(1, len(numbers) + 1):
        numbers_list += list(map(''.join, itertools.permutations(numbers,i)))

    numbers_list = set(map(int, numbers_list))
    prime_list = sieve(max(numbers_list))

    return len(numbers_list & prime_list)

References

  • 순열과 조합 - combinations, permutations