[programmers] 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.
  

Idea

처음에는 seive_of_eratosthenes algorithm을 이용해서, 일정 범위의 prime를 모두 구한다음에 하나씩 비교해보려고 했는데,
생각해 보니깐 그냥 isPrime으로도 해결이되서 isPrime으로 풀었다.

Code

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield "".join(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield "".join(pool[i] for i in indices[:r])
                break
        else:
            return

def seive_of_eratosthenes(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0], is_prime[1] = False, False

    for i in range(2, int(n**0.5)+1):
        for j in range(2*i, n+1, i):
            is_prime[j] = False

    return is_prime

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
        
    return True

def solution(numbers):
    answer = 0
    permutations_list = list()
    permutations_list_v1 = list()
    for i in range(len(numbers)):
        permutations_list.append(permutations(numbers, i+1))
    for line in permutations_list:
        for data in line:
            if data != "1":
                if not data.startswith("0"):
                    permutations_list_v1.append(data)
    permutations_list_v1 = set(permutations_list_v1)
    permutations_list_v1 = list(permutations_list_v1)
    # print(permutations_list_v1)
    
    
    for i in range(len(permutations_list_v1)):
        # print(permutations_list_v1[i])
        if isPrime(int(permutations_list_v1[i])):
            # print(permutations_list_v1[i])
            answer += 1
        else :
            pass
            
    return answer

다른사람의 코드

primeSet = set()


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

    return True


def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])


def solution(numbers):
    makeCombinations("", numbers)

    answer = len(primeSet)

    return answer

Explain

def solution(numbers):
    answer = 0
    permutations_list = list()
    permutations_list_v1 = list()
    for i in range(len(numbers)):
        permutations_list.append(permutations(numbers, i+1))
    for line in permutations_list:
        for data in line:
            if data != "1":
                if not data.startswith("0"):
                    permutations_list_v1.append(data)
    permutations_list_v1 = set(permutations_list_v1)
    permutations_list_v1 = list(permutations_list_v1)
    # print(permutations_list_v1)
    
    
    for i in range(len(permutations_list_v1)):
        # print(permutations_list_v1[i])
        if isPrime(int(permutations_list_v1[i])):
            # print(permutations_list_v1[i])
            answer += 1
        else :
            pass
            
    return answer

numbers의 length가 7이 max이므로 각각 포문을 돌면서 permutation을 생성하기로 했다.

permutations_list_v1이라는 list가 set()을 적용해서 중복값을 없애준 형태이다.
경우의수가 몇개 안되서, 괜히했나 싶지만 하는게 좋을것 같다.

마지막으로 for문에서는 isPrime()으로 prime이면 answer를 중가해준다.!