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

좋은 코드 훔쳐오기

def solution(numbers):
    Num = set()
    def perm(pick,unpick):
        if(pick!=''):
            Num.add(int(pick))
        for i in range(len(unpick)):
            perm(pick+unpick[i], unpick[:i]+unpick[i+1:])
            
    perm('',numbers)
    Num-={0,1}
    for i in range(2,int(max(Num)**0.5)+1):
        Num-=set(range(i*2,max(Num)+1,i))
    return len(Num)

관전 포인트

• itertools의 permutation을 쓰지 않고 직접 permutation을 구현하였다.
  • 원리는 ‘이미 뽑아서 만들어진 텍스트’ 와 ‘남아있는 텍스트’ 풀을 따로 가지고 for 문으로 남아있는 텍스트에서 한 문자를 뽑아, 뽑을 때마다 재귀를 돌린다.
  • 그 결과로 모든 글자 노드를 방문해야 끝나는 깊이 탐색이 이루어지면서 모든 순열이 나온다.
• 보통의 에라토스테네스처럼 모든 값을 담아 놓지 않고 필요한 문자만 set에 담아 에라토스 테네스의 체를 돌린다.
  • 반복문의 range를 생성하는 부분에서 에라토스테네스의 체와 같은 크기의 반복이 이루어지기는 한다.
• 깔끔한 set 연산
  • range를 한번에 담아 Num-=set(range(…)) 연산으로 중복을 한번에 제거한다.

내 코드

from itertools import permutations

def solution(numbers):

    MAX=int(1e4)
    Num = [True]*MAX
    Num[0], Num[1] = False, False
    primes=[]

    answer = 0
    for i in range(2,MAX):
        if(Num[i]==True):
            primes.append(i)
            k=2
            while(i*k<MAX):
                Num[i*k]=False
                k+=1

    nums = [*numbers]
    combs = set()
    for l in range(1,len(nums)+1):
        for perm in permutations(nums,l):
            combs.add(int(''.join(perm)))

    def isPrime(N):
        for p in primes:
            if(N%p==0):
                return False
        return True

    for c in combs:
        try:
            if(Num[c]):
                answer+=1
        except IndexError:
            if(isPrime(c)):
                answer+=1
    return answer

• 입력의 크기가 7자리이고 0~9인 점을 이용해 1e8까지는 에라토스 테네스의 체를 검사해야 한다고 생각하였다.
• 하지만 1e8까지 반복문을 돌리면 시간초과가 난다.
• 그래서 1e8에 square 연산을 한 1e4까지만 prime을 구하고, 그 이하 값은 바로 index를 통해 소수 여부를 반영, 그렇지 않으면 isPrime 함수에서 기존 prime들을 이용하여 소수 여부를 찾는다.
  • 위의 코드와 연산이 비슷해보이지만, 다른 점이 있다면 위의 코드는
    1. if 연산 없이 모든 수에 대해 배수를 지운다.
    2. while 문을 통한 범위 초과 검사를 하지 않아, 비교가 줄었다.