소수 찾기 - 완전탐색

 

numbers의 길이가 7이하인 것으로 보아 완전탐색으로 해도 시간이 초과되지 않을 것이란 예상을 하였다.

 

문제 해결 전략

1. 재귀함수를 통해서 숫자 카드로 만들 수 있는 모든 수를 리스트에 넣는다.
2. 리스트를 map(int,X)를 해주어 앞이 0으로 시작하는 수에서 0을 없앤다.
3. 리스트를 집합에 넣었다가 다시 리스트로 넣어주면서 겹치는 수를 없앤다.
4. 이중 포문을 통해 리스트에 있는 수들의 소수판별을 한다.
5. 이때, 나누는 수는 시간 절약을 위해 sqrt(X)까지만 한다. (* for문에서 range는 마지막 수 불포함이니까 sqrt + 1)
6. 소수에 해당할 때마다 count + 1 해준다. (* 0 과 1은 소수가 아님)

문제를 겪은 부분

1.  재귀함수 밑에 index와 temp을 다시 되돌려주어야하는 것을 까먹어서 해결하는데 오래 걸렸다.
2. 소수 판별에서 for j in range(2, int(sqrt(a1[i])) + 1) 2부터 나누어야하는 것과 range 값의 마지막은 자신을 포함하지 않으므로 1을 더해줘야한다는 사실을 처음에 생각 못했다.

 

어떻게 풀어야할지는 쉬웠지만, 실제로 구현함에 있어서는 어려움을 겪은 문제였다.

자만하지 말자!

 

소스코드

import math
def solution(numbers):
    result =[]
    index = [0]*1000001
    temp = []
    count = 0
    def recur(): # 모든 경우의 수 만드는 부분
        for j in range(len(numbers)):
            if index[j] == 0:
                index[j] = 1
                temp.append(numbers[j])
                result.append(''.join(temp))
                recur()
                index[j] = 0
                del temp[-1]


    recur() #재귀함수 호출 -> 모든 수 result에 만들기
    
    a1 = list(map(int,result)) #int화 시켜서 0으로 시작하는 숫자에서 0 제거
    a2 = set(a1) # ----]
    a1 = list(a2) # ---] 집합에 넣었다가 빼서 중복되는 수 제거
    
  
    for i in range(len(a1)): #소수 찾는 부분
        flag = 0
        for j in range(2,int(math.sqrt(a1[i]))+1): # 2부터 자신의 제곱근까지만 탐색
            if a1[i] % j == 0:
                flag = 1
        if a1[i] == 0 or a1[i] == 1:
            pass
        elif flag == 0:
            count += 1
    return count