[프로그래머스] 🕵️‍♀️ 소수 찾기 / python

반응형

🕵️‍♀️ 소수 찾기 문제 풀어보기

😃 나의 코드

from itertools import permutations 

def solution(numbers):
    answer = set()
    maximum = 10000000
    prime_lst = [False, False] + [True] * maximum
    for idx, num in enumerate(prime_lst):
        if num:
            k = idx*2
            while k <= maximum:
                prime_lst[k] = False
                k += idx
    for i in range(1, len(numbers)+1):
        perm = permutations(list(numbers), i)
        for i in list(perm):
            num = int("".join(list(i)))
            if prime_lst[num]:
                answer.add(num)
    return len(answer)

완전 탐색^{exhaustive search}를 이용하여 푸는 문제입니다. 문제는 두 개의 문제로 나눠서 풀 수 있습니다. 해당 숫자가 소수인지 판별하는 문제와 숫자로 된 배열로 나올 수 있는 모든 숫자를 얻는 문제입니다.

문제의 조건인 숫자가 최대 7자리때문에 미리 10^7이하의 모든 소수를 찾는 과정을 먼저 진행합니다. 여기선 2부터 시작하는 연속된 자연수를 미리 써 두고, 처음 나타나는 수의 배수들을 모두 지우는 식으로 소수를 남기는 방식인 에라토스테네스의 체를 이용합니다. 이 방법은 나올 수 있는 모든 숫자를 찾은 뒤 그 숫자가 각각 소수인 지 확인하는 식으로 푸는 대신에 더 빠른 방법입니다.

다음은 숫자로 된 배열로 나올 수 있는 숫자를 구하는 문제입니다. Python의 내장 모듈인 itertools의 permutations를 이용해서 순열을 사용할 수 있습니다. permutation의 인자는 list와 r로 list에 있는 데이터를 순서를 생각해서 r개 뽑게 합니다. 이를 이용하여 1개부터 numbers의 크기까지 permutations를 이용해서 새로운 숫자 조합을 만듭니다. permutation의 결과값인 tuple을 list로 바꾸고 join을 이용해서 string으로 만들고 최종적으로 int를 이용해 정수로 만들어줍니다.

이제 이 정수값을 미리 제작해놓은 소수를 판별하는 배열인 prime_lst에 넣어 소수 여부를 파악하고 중복을 방지하기 위해 set에 넣어줍니다. 마지막으로 set의 크기를 반환하면 문제가 마무리됩니다.

반응형

저작자표시

'Algorithm > Problem Solving' 카테고리의 다른 글

[프로그래머스] 👨‍🏫 정수 삼각형 / python  (0)	2019.02.18
[프로그래머스] ⚾ 숫자 야구 / python  (4)	2019.02.15
[프로그래머스] 🕵️‍♀️ 소수 찾기 / python  (0)	2019.02.15
[프로그래머스] 🎨 카펫 문제 / python  (1)	2019.02.15
[프로그래머스] 👩‍🏫 모의고사 / python  (0)	2019.02.15
[프로그래머스] 👨‍🏫 가장 큰 정사각형 / Python  (0)	2019.02.15