[Programmers] 완전탐색 소수 찾기

문제. 완전탐색 > 소수 찾기

---

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

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

 

제한사항

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

입출력 예 설명

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

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

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

출처 : 프로그래머스 Level 2 소수 찾기

---

나의 풀이

from itertools import permutations

def solution(s):
    answer = 0

    new_s = list(s)
    for i in range(2,len(s)+1):
        pm = list(permutations(s, i))
        for j in pm:
            if len(j) <= len(s):
                new_s.append(''.join(j))
    # s에 입력되는 수로 만들 수 있는 모든 수를 list화
    new_s = list(set([int(x) for x in new_s]))
    
    for i in range(2):
        if new_s.count(i):
            new_s.remove(i)
    # 0과 1의 경우, 소수로 볼 수 없으니 제거
    
    for x in new_s:
        i = 2
        while i**2 <= x: 
            if x % i == 0:
                answer -= 1
                break
            i+=1
        answer += 1
    
    return answer

이번 문제의 경우, level 1에 있는 소수 찾기 문제와는 조금 다르게 permutation을 이용하여 입력에 해당하는 숫자의 조합까지 고려해야 해서 조금 까다로운 부분이 많은 문제였습니다.

 

다른 사람의 풀이

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을 이용하여 에라토스테네스 체를 멋지게 사용한 것을 알 수 있었습니다. 또한, 제가 고민한 코드보다 훨씬 간결하고 명료하여서 배울 수 있는 점이 많았던 문제여서 아직 부족한 자신을 돌아볼 수 있어서 좋았습니다.