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

내 코드

def solution(numbers):
    import itertools
    
    answer = 0
    a = []
    
    l = [i for i in str(numbers)]
    
    for i in range(1,len(l)+1):
        b = list(itertools.permutations(l,i))
        a += [int("".join(i)) for i in b]
    
    a = set(a)
    
    for i in a:
        if i<2: continue
        for j in range(2,i):
            if i%j==0:
                break
        else:
            answer+=1
            
    return answer

17이라는 문자열이 주어졌을때 1,7으로 만들 수 있는 숫자를 구해 소수의 갯수를 찾는 문제이다.

 

두번째 테스트케이스인 011를 예시로 들며 풀이 과정을 설명하겠다. 

011이라는 문자열은 [0,1,1]로 만든다. 리스트로 만든 다음 순열을 사용하여 만들 수 있는 숫자들을 구한다.

import itertools를 하고 permutations를 사용하여 리스트 중 숫자 하나를 뽑을 때, 두개를 뽑을 때.. 이렇게 리스트의 길이까지 for문을 돌려 만들 수 있는 숫자를 구했다. permutations를 사용하면 [(1,7),(7,1)] .. 이런식으로 나오기 때문에 튜플안에 있는 수를 join을 사용하여 합쳐주고 int형으로 바꿔서 a에 넣었다.

중복된 수를 제외하기 위해서 set을 하용하였고 구한 숫자로 소수를 구하였다.

 

다른사람 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

이 풀이는 list를 사용하지 않고 바로 set을 사용하여 푼 풀이다.

나는 n을 for문을 사용하여 리스트로 만들어주었는데 이 풀이는 list(n)하여 바로 리스트로 만들었다. list("17")을 하면 ["1","7"]이렇게 된다. 이렇게 만든 list를 permutations를 사용하여 순열을 구해준다. 나는 list에 더하는 방식으로 풀었는데 이 풀이는 set에 합하는 방식으로 풀었다. 

소수를 구해야 하니 set에서 0,1은 제거해준다.

2이상 부터는 에라토스테네스의 체를 사용한다. 백준에서 한번했었던건데.. 다음부턴 소수구할때 에라토스테네스 방법을 쓰자.,,