[프로그래머스] 완전 탐색 - 소수 찾기

 

나의 답

import itertools

def prime(n): # 소수 판별 함수
    
    if n==1 or n==0:
        return False
    
    for i in range (2, n):
        if n%i==0:
            return False
    return True

def solution(numbers):
    dic = {}
    
    
    for i in range (1, len(numbers)+1):
        listA = list(itertools.permutations(numbers, i)) #글자가 n(1~numbers의 길이)개일 때 순열 생성
        
        for a in listA:
            n = ''.join(list(a)) #문자인 숫자 조합을 문자열로 바꿈
            
            if prime(int(n)): #문자열을 숫자로 바꿔, 소수인지 판별
                dic[int(n)]=1 # 소수가 맞으면, dic key로 설정, 같은 값이어도 같은 key에 저장
    
    print(dic)
    return len(set(dic)) # dic의 길이 == 소수의 개수

 

또 곧이 곧대로 문제를 풀었다..

순열만들어주는 기능을 처음 써봤는데, 신세계다

dic를 써서 중복되는 걸 제거해봤는데, 리스트로 만들어서 set 셋팅을 해줘도 시간은 비슷하게 흘르는 것 같다.

효율성은 0인 코드이겠지..^^

 

다른 사람 답

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)

 

에라스토테네스 체를 사용했다고 한다..

set(map(데이터형, map(문자열)) 이렇게 한 줄에 쓸 수가 있구나..

아직 한 줄에 저렇게 줄여쓰는 건 너무 헷갈린다. ㅎ.ㅎ

대단하시다