[프로그래머스] Lv.2 소수 찾기

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

프로그래머스

 

 

1. 해결 방법

일단 본인은 DFS 방법으로 완전탐색(백트래킹)을 해결하였다.

dfs 시작은 "" 빈 문자열을 매개 변수로 재귀를 돌렸고, numbers를 리스트로 만들어서 하나 하나 탐색을 한 후 word + numbers[i]를 매개 변수로 재귀를 돌렸다.

종료 지점은 for문을 이용해서 숫자가 1자리 일때부터 len(numbers) 까지 돌리고 방문 체크도 해주면 모든 경우의 수가 나오게 된다.

여기서 포인트는 set() 메서드를 사용해서 중복을 없애주어야 한다.

 

 

2. 정답 코드

(1) DFS

def solution(numbers):
    answer = 0
    
    def dfs(word):
        if len(word) == i:
            result.append(word)
            return 
        
        for j in range(len(numbers)):
            if chk[j] == False:
                chk[j] = True
                dfs(word + numbers[j])
                chk[j] = False
            
        
    numbers = list(numbers)
    chk = [False] * (len(numbers) + 1)
    result = []
    for i in range(1, len(numbers) + 1):
        dfs("")
        
    result = list(set(map(int, result)))
        
    for num in result:
        num = int(num)
        if num == 1 or num == 0:
            continue
            
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            answer += 1
            
                
    return answer

 

(2) permutations

def solution(numbers):
    from itertools import permutations
    answer = 0
    
    result = []
    for i in range(1, len(numbers) + 1):
        result += list(set(map(''.join, permutations(numbers, i))))
        
    result = list(set(map(int, result)))
        
    for num in result:
        if num == 1 or num == 0:
            continue
            
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            answer += 1
            
                
    return answer