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

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

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

처음에 numbers에 있는 숫자들에 대해 모든 경우의 수를 구해야 한다. 

이 문제를 풀고 나서 다른 사람들의 풀이를 보니 다양한 방법이 존재했다.

나는 itertools모듈의 permutations함수를 사용했다.

 

1. numbers에 있는 숫자를 num배열에 넣고 dab에도 넣어준다. (한자리 수는 따로 처리)

    -> permutations(num, 1)을 하면 [('1', ), '('0', )]이런식으로 뭔가 이상하게 나와서 따로 처리해주었다.(좀 더 공부해봐야 할듯...)

2. i가 2부터 len(numbers)까지 돌며 num배열안에 있는 숫자들 중 i개를 골라 만들 수 있는 모든 경우의 수를 dab에 넣어주었다.

   중복된 수는 필요없으므로 중복을 허용하지 않는 set자료형을 사용했다.

 

3. get_primes()함수는 에라토스테네스의 체 알고리즘을 사용해서 소수를 판별하는 함수이다.

   최대로 들어올 수 있는 수가 9999999이므로 9999999까지 배열을 만들고 소수에 해당하는 인덱스 말고 나머지는 False로 바꿔준다.

 

4. 결국 dab에는 numbers에 있는 수들로 이루어진 모든 경우의 수가 들어가므로 dab배열(?) 안에 있는 수를 돌며

    is_prime[i]가 True이면 소수이므로 cnt에 1을 더해준 뒤 return 해주면 끝

from itertools import permutations
import math
def solution(numbers):
    num, dab = [], set()
    cnt = 0
    def get_primes():
        is_primes = [False, False] + [True] * 9999999
        max_length = math.ceil(math.sqrt(9999999))
        for i in range(2, max_length):
            if is_primes[i]:
                for j in range(i+i, 9999999, i):
                    is_primes[j] = False
        return is_primes
    
    for i in numbers:
        num.append(i)
        dab.add(int(i))
        
    for i in range(2, len(numbers) + 1):
        for k in list(permutations(num, i)):
            tmp = ''
            for j in range(len(k)):
                tmp += k[j]
            dab.add(int(tmp))

    is_prime = get_primes()
    for i in dab:
        if is_prime[i]:
            cnt += 1
            
    return cnt

 

(프로그래머스 level2)

 

# itertools모듈을 좀더 공부해보자!