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

📃 문제 설명

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

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

💻 문제 풀이

import math
from itertools import permutations

def is_prime_number(n):
    """소수판별 함수"""
    if n==0 or n==1:                                # 0,1 은 소수가 아님
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):   # sqrt(n)까지만 for문을 돌면서 확인하면 된다.
            if n % i == 0:                          # 2~sqrt(num)까지 나누어 떨어지는 숫자가 있으면 소수가 아님
                return False
        
        return True                                 # for문을 다 돌았는데도 False가 아니면 소수

def solution(numbers):
    answer = []
    for i in range(1, len(numbers)+1):              
        arr = list(permutations(numbers, i))        # permutations(순열)을 사용해 i개씩 묶어지는 list 생성
        for j in range(len(arr)):                   # 생성한 list(arr) 길이만큼 for문 실행
            num = int(''.join(map(str,arr[j])))     # list(arr)의 값들은 tuple들로 되어있으모 join(map(str,))을 사용해 join해준다
            if is_prime_number(num):                
                answer.append(num)                  # is_prime_number() 함수가 True일 경우 (= 소수일 경우) num 추가
    
    answer = list(set(answer))                      # 같은 값이 나올 수 있기 때문에 set()을 통해 중복값 제거
    return len(answer)
    

print(solution("17"))       # result : 3
print(solution("011"))      # result : 2

중요 포인트

• permutations(순열)을 사용해 문제 풀이
• ''.join(map(str,arr[j])) 를 사용해 tuple을 join
• 소수를 찾는 반복문에서 범위를 2~sqrt(n) 로 지정

📌 순열과 조합 라이브러리

1. 순열(permutations)

permutations(반복 가능한 객체, n) // n=몇개를 뽑을 것인지

• 중복을 허용하지 않는다.
• 순서에 의미가 있다 (= 같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수로 판단)

from itertools import permutations

print(list(permutations([1,2,3,4], 2)))
print(list(permutations([1,2,3,1], 2)))

# result1
# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

# result2
# [(1, 2), (1, 3), (1, 1), (2, 1), (2, 3), (2, 1), (3, 1), (3, 2), (3, 1), (1, 1), (1, 2), (1, 3)]

2. 중복 순열(product)

product(반복 가능한 객체, repeat=num)

• 중복을 허용하는 순열

from itertools import product

print(list(product([1,2,3,4], repeat=2)))
print(list(product([1,2,3,1], repeat=2)))

# result1
# [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)]

# result2
# [(1, 1), (1, 2), (1, 3), (1, 1), (2, 1), (2, 2), (2, 3), (2, 1), (3, 1), (3, 2), (3, 3), (3, 1), (1, 1), (1, 2), (1, 3), (1, 1)]

3. 조합(combinations)

combinations(반복 가능한 객체, n) // n=몇개를 뽑을 것인지

• 중복을 허용하지 않는다.
• 순서에 의미가 없다 (= 같은 값이 뽑히면 같은 경우의 수로 판단)

from itertools import combinations

print(list(combinations([1,2,3,4], 2)))
print(list(combinations([1,2,3,1], 2)))

# result1
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

# result2
# [(1, 2), (1, 3), (1, 1), (2, 3), (2, 1), (3, 1)]

4. 중복 조합(combinations_with_replacement)

combinations_with_replacement(반복 가능한 객체, n) // n=몇개를 뽑을 것인지

• 중복을 허용하는 조합

from itertools import combinations_with_replacement

print(list(combinations_with_replacement([1,2,3,4], 2)))
print(list(combinations_with_replacement([1,2,3,1], 2)))

# result1
# [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)]

# result2
# [(1, 1), (1, 2), (1, 3), (1, 1), (2, 1), (2, 2), (2, 3), (2, 1), (3, 1), (3, 2), (3, 3), (3, 1), (1, 1), (1, 2), (1, 3), (1, 1)]