[python3] 프로그래머스 레벨 2 - 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3 

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

 

# 최종 답안

import itertools

def find_decimal(number):
    if number == 1:
        return 1
    elif number == 0:
        return 1
    for i in range(2, number):
        if number % i == 0:
            return 1
    return 0

def solution(numbers):
    answer = 0
    
    num_list = []
    
    for i in range(len(numbers)):
        num_list.append(numbers[i])
    
    a = []
    for i in range(1, len(numbers)+1):
        a.append(list(itertools.permutations(num_list, i)))
    answer_list = []
    for i in a:
        for j in i:
            tmp = ""
            for k in j:
                tmp += k
            if find_decimal(int(tmp)) == 0:
                answer_list.append(int(tmp))
     
    answer_set = set(answer_list)
    answer_list = list(answer_set)
    return len(answer_list)

 

 

문자열로된 숫자 numbers를 받고, 1의 자리수로 쪼개서 만들수 있는 소수의 갯수를 세는 문제.

itertools의 permutation을 이용하여 1의 자리로 만들수 있는 모든 가짓수의 순열을 얻음. 이 때 문제는 중복되는 수가 존재함.(0 , 1,  1의 경우 11과 011이 중복, 이외에도 엄청 많다)

그래서 일단 모든 가짓수를 구하고 -> 중복을 없애고 -> 중복 없는 가짓수에 대한 소수 찾기를 수행하면 된다.

(제 코드는 가짓수를 구하고 -> 소수 찾고 -> 중복을 없애는 순, 비효율적임...)

 

다른 사람의 풀이

1. set을 적극적으로 이용하여 합집합 차집합으로 경우의 수를 없애고 더함.

2. 에라토스 테네스의 채를 이용하여 조금더 효율적으로 코딩함.