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

🧑🏻‍💻 문제링크

문제풀이

순열과 수학 개념을 사용한 완전 탐색 문제로 어떤 수의 문자열이 주어졌으면 모든 경우를 구한 다음에 그 값이 소수인지 아닌지 확인하는 문제이다. 파이썬에서 조합을 찾는 라이브러리는 다음과 같다.

from itertools import permutations

요 permutations이 순열을 나타낸다. 그리고 자매품 combinations 도 존재한다.

이 둘의 차이점은 다음과 같다.

먼저,permutations(순열)은 순서를 고려하기 때문에 리스트에서 n개의 원소를 골라 나열된 경우의 수가 나오게 된다.

# Permutations
from itertools import permutations

arr = ['A', 'B', 'C']
nPr = permutations(arr, 2)
print(list(nPr))

>> [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

combinations(조합)은 서로 다른 n개 중에서 r개를 취한 조합이다. 조합은 순서를 고려하지 않기 때문에 다음과 같은 결과가 출력된다.

# Combinations
from itertools import combinations

arr = ['A', 'B', 'C']
nCr = combinations(arr, 2)
print(list(nCr))

>> [('A', 'B'), ('A', 'C'), ('B', 'C')]

코드

from itertools import permutations

# 소수 구하기
def isPrime(n):
    if n < 2:
        return False
    
    for i in range(2, n):
        if n % i == 0:
            return False
        if i * i > n:
            break
    return True

def solution(numbers):
    answer = []
    
    for i in range(1, len(numbers)+1):
        # numbers에 대한 모든 경우의 수를 만들어줌
        temp = list(map(''.join, permutations(numbers, i)))
        # 리스트에서 중복을 제거하고 소수를 구함
        for j in list(set(temp)):
            # 소수가 맞으면 answer에 넣음
            if isPrime(int(j)):
                answer.append(int(j))

    answer = len(set(answer))
    
    return answer

결과