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

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

---

1. 풀이

• 모든 가능한 순열을 구하자

011이 주어졌을 때 가능한 모든 조합

위 그림처럼 011이 입력으로 주어지면, 길이가 각 1, 2, 3인 다양한 순열이 존재한다. 순서가 중요하기 때문에 조합이 아니라 순열을 구해야 한다. 각 숫자는 문자열로 취급하므로 011이라는 것이 존재할 수 있다.

 

 

• 각 순열로 만들어진 숫자가 소수인지 판별하자 (with 집합)

위에서 만들어진 모든 조합을 int 타입으로 형변환하고, 이것이 소수인지 판별하자. 소수일 때만 answer라는 집합(set)에 담고, 아니면 담지 않는다. 리스트 대신 집합을 사용하는 이유는, 서로 다르게 조합해서 만들어진 결과가 똑같은 수일 수 있기 때문이다. 중복을 제거하기 위해 집합을 사용한다.

최종적으로 집합의 길이를 반환하면 정답이다.

 

 

 

2. 정답 코드

import math

def solution(numbers):
    length = len(numbers)
    answer = set()

    for i in range(1, length + 1):
        visited = [False] * length
        permutate(0, i, '', visited, length, numbers, answer)
    return len(answer)

def permutate(index, depth, result, visited, length, numbers, answer):
    if index >= depth:
        if is_prime(int(result)):
            answer.add(int(result))
        return
    
    for i in range(length):
        if visited[i]: continue
        
        visited[i] = True
        permutate(index + 1, depth, result + numbers[i], visited, length, numbers, answer)
        visited[i] = False

def is_prime(k):
    if k <= 1:
        return False
    for x in range(2, int(math.sqrt(k)) + 1):
        if k % x == 0:
            return False
    return True