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

Programmers, 소수 찾기

TL;DR

• DFS(깊이 우선 탐색)

문제 요약

1. 한 자리 숫자가 적힌 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내는 함수를 작성하라.

 

- 주어진 숫자들로 만들 수 있는 모든 경우의 숫자들 중에서 소수의 개수를 반환하는 프로그램을 찾으면 된다.

- 깊이 우선 탐색(DFS)을 사용해서 만들 수 있는 숫자들의 조합을 찾으면 문제를 해결할 수 있다.

입출력 형태

입출력 예시

풀이

import math

def solution(numbers):
    answer = 0
    permutations = set()
    prev_elements = []
    
    def dfs(elements):
        if ''.join(prev_elements) != '':
            permutations.add(int(''.join(prev_elements[:])))
        
        for e in elements:
            next_elements = elements[:]
            next_elements.remove(e)
            
            prev_elements.append(e)
            dfs(next_elements)
            prev_elements.pop()

    dfs(list(numbers))
    for p in permutations:
        if p == 0 or p == 1:
            continue
        flag = True
        for i in range(2, int(math.sqrt(p)) + 1):
            if p % i == 0:
                flag = False
                break
        if flag:
            answer += 1
    return answer

 

DFS 를 함수로 작성하여 주어진 숫자들로 만들 수 있는 숫자들을 만든다.

- prev_elements가 주어진 numbers를 통해 만들 수 있는 숫자들을 저장한다. 이 때, 아무 원소가 들어가 있지 않은 경우는 추후 다시 숫자형으로 변환할 때 에러가 발생할 수 있으므로 제외해주었다.

- 중복 원소들이 나올 수 있기 때문에 이를 처리하기 위해서 만든 숫자들을 저장할 permutations는 set으로 선언하였다.
- 변수로 받은 elements의 각 원소에 대해서 재귀적으로 수행된다.

  - 재귀적으로 수행될 때는 현재 조회한 원소를 제외한 나머지 원소들을 갖고 숫자들을 조합할 수 있도록 next_elements를 만들어 변수로 넣어주었다.

  - 재귀적으로 호출되고 나서는 해당 숫자로 만들 수 있는 숫자들을 모두 만든 것이므로 pop해준다. 이를 해주지 않을 경우 계속해서 길어지는 숫자 조합이 만들어진다.

- DFS를 수행하고 나면 permutations에는 주어진 숫자들을 조합해서 만든 숫자들이 set에 저장된다.

 

만든 숫자들 중 소수가 아닌 0과 1을 제외하고 나머지 수들에 대해서 소수 여부를 판단한다.

- 소수 판별을 할 때는 자기 자신까지 나누어 떨어지는 수를 확인할 필요 없이 자기 자신을 제곱근한 수까지 확인하면 소수 여부를 훨씬 더 빠르게 판별할 수 있다. 이를 위해 `int(math.sqrt(p)) + 1` 구문이 사용되었다.

- 소수일 경우는 소수의 수를 나타내는 answer를 증가시켰다.

 

측정한 소수의 개수를 반환한다.

다른 풀이

- 파이썬에서 제공하는 `itertools`의 `permutations` 메소드를 사용해서도 문제를 해결할 수 있다.