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

answer = 0
adder = []
allsentence = {'0', '1'}

def finder(string):
    global answer
    if len(string) > 0:
        num = int(string)
    else: 
        return
    
    if num in allsentence :
        return
    allsentence.add(num)
    
    if num == 0 or num == 1:
        return
    
    flag = 0
    for i in range(2, num//2 + 1):
        if num%i == 0:
            flag = 1
    if flag == 0:
        adder.append(string)
        # answer += 1

def dfs(cnt, visit, numbers, string):
    global answer
    
    # 종료조건 : cnt가 numbers의 length에 다다랐을 때
    if cnt == len(numbers):
        finder(string)
        return
    
    finder(string)
    
    for i in range(len(numbers)):
        if visit[i] == 0:
            visit[i] = 1
            dfs(cnt+1, visit, numbers, string + numbers[i])
            visit[i] = 0

def solution(numbers):
    global answer
    length = len(numbers)
    
    visit = [0] * length
    arr = []
    
    dfs(0, visit, numbers, "")
    
    for i in range(len(adder)):
        adder[i] = int(adder[i])
    lst = list(set(adder))
    
    return len(lst)

주의할 점

 

완전탐색 - DFS

최단거리 - BFS 로 푸는거다