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

참고: https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

주어진 numbers의 숫자로 숫자 조합을 만들 때,

각 조합에 해당하는 숫자가 소수인 경우를 카운트하는 문제이다.

 

from itertools import permutations

def is_prime(x):
    if x == 0 or x == 1:
        return False
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

def solution(numbers):
    data = list(map(str, numbers))
    result = []
    for i in range(1, len(data)+1):
        result.append(list(set(permutations(data, i))))
    
    new = []
    for i in range(len(result)):
        for j in range(len(result[i])):
            new.append(int(''.join(result[i][j])))
            
    new = list(set(new))
    answer = 0
    for i in range(len(new)):
        if is_prime(new[i]) == True: answer+=1
        
    return answer

 

다음과 같이 순열을 이용하여 문제를 풀었는데,

주어진 numbers를 리스트로 쪼개어 순열을 만들어준다.

해당 조합된 순열을 문자열로 합치고, int형으로 형변환하여

 

새로운 new 리스트에 추가해준 뒤 중복을 제거한다.

(11과 011은 같은 숫자로 취급해야하기 때문에 제거한다)

 

new 리스트를 돌면서 소수인지 검사하여 True이면

answer 값에 1씩 추가하여 리턴하였다.

 

더 간단한 풀이가 있나해서 찾아보는데,

에라토스테네스 체를 이용하여 빠르게 소수를 찾는 방법도 있다..

 

화이팅 💪