[프로그래머스] 소수 찾기 파이썬

[프로그래머스] 소수 찾기

---

✔️문제

분류

완전 탐색

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

✔️풀이

❌테스트 케이스 2, 10, 11, 12번 틀린 코드

import itertools

def solution(numbers):
    answer = 0
    arr = set()
    for i in range(1, len(numbers)+1):
        for a in itertools.permutations(numbers, i):
            num = int(''.join(a))
            if num != 1 and num != 0:
                arr.add(num)
    for a in arr:
        b = True
        for i in range(2, int(a**(1/2))):
            if a%i==0:
                b = False
                break
        if b:
            answer += 1
    return answer

1. itertools의 permutations를 이용해서 만들 수 있는 조합을 찾았다.
2. 해당 조합으로 만들어질 수 있는 수들 중 0과 1을 제외한 숫자들로 집합 arr를 만들었다.
3. 반복문을 돌면서 소수를 찾아준다.

✅맞은 풀이

import itertools

def solution(numbers):
    answer = 0
    arr = set()
    for i in range(1, len(numbers)+1):
        for a in itertools.permutations(numbers, i):
            num = int(''.join(a))
            if num != 1 and num != 0:
                arr.add(num)
    for a in arr:
        b = True
        for i in range(2, int(a**(1/2))+1):
            if a%i==0:
                b = False
                break
        if b:
            answer += 1
    return answer

소수를 찾아줄 때, int(a**(1/2))+1로 범위를 수정해주었다.
너무 당연한건데 놓치다니..!!

💡새로 알게된 내용

Python의 itertools를 이용하면 순열과 조합을 for문 없이 구현할 수 있다.

순열 permutation

import itertools

arr = itertools.permutation([1,2,3], 2)

조합 combination

import itertools

arr = itertools.combination([1,2,3], 2)