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

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

프로그래머스

이 문제는 테크닉이 필요한 문제이다. 아마 대부분 정답을 찾아도 틀리분들은 테스트 몇개가 통과가 안됐을 것이다.

그 이유는 바로 소수를 검증하는 과정에서 문제가 있는것일거다.

필자의 경우 예를들어 24 라는 수를 소수인지 검증하기 위해 1부터 24까지 반복문을돌려 하나씩 나눠가며 소수를 판단했다.

이런 방식으로 소수를 검증했다면 "틀린다." 이유는 1부터 24까지 수를 다 넣어가며 소수를 검증하는것은 "비효율"적이기 때문이다.

1*24 = 24

2*12 = 24

3*8 = 24

4*6 = 24

사실상 2,3 까지만 검사를 해줘도 그 뒤는 2,3으로도 나뉘어지는 수들이기 때문에 할 필요가 없다. 즉, 검증하고자 하는 수의 제곱근 까지만 검사를 해주면 비효율을 피할수있다.

아래는 풀이코드이다.

import math
def solution(numbers):
    answer = 0
    arr = list(numbers)
    visited = [False]*len(arr)
    ans = []
    def check(n):
        cnt=0
        if n == 1 or n == 0:
            return False
        # sqrt 함수를 사용하여 소수 검사의 범위를 줄여줘야 시간초과가 발생하지 않는다.
        # 해당 숫자의 제곱근의 이하의 수만 검사를 해줘도 그 수가 소수인지 아닌지 판별 할 수 있다.
        # 굳이 모든 숫자를 검사 해줄 필요가 없다!!
        for i in range(2,int(math.sqrt(n))+1): 
            if n%i == 0:
                cnt+=1
        if cnt == 0 :
            return True
        else:
            return False
    number=""
    def dfs(number):
        nonlocal answer        
        if number and check(int(number) or len(number) == len(arr)): 
            n = int(number)
            if n not in ans:
                ans.append(n)
        for i in range(len(arr)):
            if visited[i] == True:
                continue
            visited[i] = True
            number+=arr[i]
            dfs(number)
            number=number[:-1]
            visited[i] = False
            
            
    dfs(number)      
    answer = len(ans)
    return answer