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

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

코딩테스트 연습 - 소수 찾기

 

1️⃣ DFS를 사용해서 풀이했다.

2️⃣ 숫자의 자릿수가 numbers의 자릿수보다 크면 안 되므로, 레벨이 numbers의 자릿수보다 더 커지면 리턴해주었다.

3️⃣ num이 최초의 상태('')가 아니고, DFS의 변수로 check 배열을 두어 check 안에 없는 수만 검사해주었다.

4️⃣ 시간 초과로 답이 안 나와서 소수 검사하는 for문 안에 break를 넣어줬더니 제대로 답이 나왔다.

 

def solution(numbers):
    answer = 0
    visit = [0]*len(numbers)
    def dfs(level, num, check):
        nonlocal answer
        if level == len(numbers)+1:
            return
        flag = 0
        if num != '' and int(num) > 1 and int(num) not in check:
            for i in range(2, int(num)):
                if int(num)%i == 0:
                    flag = 1
                    break
            if flag == 0:
                answer += 1
                check.append(int(num))
        for idx in range(len(numbers)):
            if visit[idx] == 1:continue
            new_num = num+numbers[idx]
            visit[idx] = 1
            dfs(level+1, new_num, check)
            visit[idx] = 0
    dfs(0, '', [])
    return answer