프로그래머스 - 소수 찾기(완전 탐색)

문제

---

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

 

풀이

---

문자열로 만들 수 있는 숫자를 완전탐색을 활용해서 다 구한 다음 그 숫자가 소수가 가능한지 판단해야 하는 문제라고 생각하고 접근을 했다.

즉, 문자열을 완전탐색해서 가능한 숫자를 다 구해주는 함수 + 소수인지 판단하는 로직, 이 두가지가 필요하다고 생각했다.

 

📌 소수를 판단하는 로직

def isPrime(n):
	if n==1 or n==0:
		return False
	for i in range(2,int(n**0.5)+1):
    	if n%i==0:
        	return False
	return True

자연수에 존재하는 약수의 원리를 이용한 코드이다.

1과 자기자신을 제외해서 약수가 존재하는지 확인하려면, 자기자신의 루트값까지만 확인을 하면 된다.

어짜피 약수들은 대칭적으로 짝을 이루기 때문이다.

8이라는 숫자가 있다고 예를 들면,

8의 약수는 1,2,4,8이 있는데 이들은 1x8, 2x4, 4x2, 8x1로 짝을 이룬다. 그러므로 루트 8의 값이 약 2.xx이므로 2까지만 나누어 떨어지는지 확인한다.

1과 0은 소수가 아니므로 무조건 False를 반환하도록 한다.

 

 

📌 문자열을 완전탐색해서 가능한 숫자를 다 구해주는 로직

 

아래와 같이 2가지 방법으로 구할 수 있다.

  ✔️ dfs로 재귀함수를 이용

    numbers=["1","0","0"]
    visited = [False] * len(numbers)
    
    def dfs(word, k):
        if len(word) == k:
            result.add(int(word))
            return
        else:
            for i in range(len(numbers)):
                if visited[i] == False:
                    visited[i] = True
                    dfs(word + numbers[i], k)
                    visited[i] = False

    for k in range(1, len(numbers) + 1):
        dfs("", k)

 

 ✔️ 파이썬의 permutations를 이용

from itertools import permutations

numbers="011"
arr=list(numbers)
result=[]

for i in range(1,len(arr)+1):
    result+=list(permutations(arr,i))

answer=[int(("").join(res)) for res in result]
answer=set(answer)
print(answer)

 

 

전체 코드

---

dfs를 이용한 코드이다.

def solution(numbers):
    result = set()

    numbers = list(numbers)
    visited = [False] * len(numbers)

    def dfs(word, k):
        if len(word) == k:
            result.add(int(word))
            return
        else:
            for i in range(len(numbers)):
                if visited[i] == False:
                    visited[i] = True
                    dfs(word + numbers[i], k)
                    visited[i] = False

    for k in range(1, len(numbers) + 1):
        dfs("", k)

    def isPrime(n):
        if n==1 or n==0:
            return False
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                return False
        return True

    answer = 0
    for number in result:
        if isPrime(number)==True:
            answer+=1

    return answer

 

 

링크

---

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python 

프로그래머스