완전탐색
알고리즘 문제에는 BFS와 DFS 처럼 효율적인 탐색방법을 사용하는 경우가 많지만 처음부터 끝까지 for문을 돌려 완전탐색하는 것이 오히려 효과적인 경우가 있다.
문제
소수찾기
https://programmers.co.kr/learn/courses/30/lessons/42746?language=cpp
문제
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
예시
##numbers, return
17 3
011 2
풀이
주어진 숫자로 모든 조합의 숫자를 만드는 것이 포인트이다. 소수인지 검사하는 방법은 조합된 숫자까지 for문을 돌려 나누어지는 값이 있는지 확인해보면 되기 때문에 크게 어렵지 않다. 만들 수 있는 경우의 수는 다음과 같다.
${n}P{1}, {n}P{2}, {n}P{3}, {n}P{4}, …, {n}P{n}$
# 소수 확인, (2 ~ 자기자신-1)로 나눠서 나머지가 있는지 확인
def check(number):
prime = True
for i in range(2, number):
if number % i == 0:
prime = False
return prime
return prime
def permut(arr, n):
# 1. visited 설정
visited = [0 for _ in range(len(arr))]
num_list = []
def make(chosen, visited):
# 2. 원하는 만큼 (n) 채워지면 return
if len(chosen) == n:
number = ''
for k in chosen: number = number + k
num_list.append(int(number))
return
# 3. for문 arr 길이만큼 (가장 처음에 선택되는 숫자가 돌아가기 위해)
for i in range(len(arr)):
if not visited[i]:
# 4. 선택 및 visited 체크
chosen.append(arr[i])
visited[i] = 1
# 5. 재호출
make(chosen, visited)
# 6. back
visited[i] = 0
chosen.pop()
make([], visited)
return num_list
def solution(numbers):
answer = 0
list_number = list(numbers)
new_list = []
for i in range(len(list_number)):
new_list = new_list + permut(list_number, i+1)
# 중복제거
new_list = set(new_list)
# 소수 검사
for num in new_list:
if num != 1 and num != 0 and check(num):
answer = answer + 1
return answer