[프로그래머스] Level 2_소수 찾기(완전탐색)

📌문제 유형

완전탐색

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도(58.3)

from itertools import permutations

def solution(numbers):
    answer = 0
    num_list = []
    
    # 숫자가 하나인 경우
    for num in numbers:
        if num == '0':
            break
        for i in range(2,int(num)):
            if int(num) % i == 0:
                break
            if i == int(num) - 1:
                num_list.append(num)
    
    # 숫자가 두 개 이상인 경우
    for i in range(2,len(numbers)+1):
        p = list(permutations(numbers,i))
        
        for j in range(len(p)):
            num = int(''.join(p[j]))
            
            for k in range(2,num):
                if num % k == 0:
                    break
                if k == num-1:
                    num_list.append(num)
            
    return len(set(num_list))

2차 시도(다른사람 풀이 참조)

 - dfs 이용(재귀함수)

•  소수인지 체크하는 함수 따로 만들기
• 숫자 하나만 확인하고, search_numbers를 이용하여 두 개 이상 숫자를 붙이는 경우도 확인하기
  • search_numbers에서 rem이 남아있을 경우, 재귀함수 사용

+) replace(j, ' ', 1) 사용 예시

파이썬 replace( ) 문자열을 변경하는 함수 (Python)

# 소수인지 아닌지 체크
def chk_prime(number):
    if number == 0 or number == 1:
        return False
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

# 두 개 이상 숫자를 붙이는 경우
def search_numbers(numbers, i, chk_nums, prime_list):
    for j in numbers:
        num = i + j
        rem = numbers.replace(j, '', 1)
        if int(num) not in chk_nums:
            chk_nums.append(int(num))
            if chk_prime(int(num)):
                prime_list.append(int(num))
        if rem:
            search_numbers(rem, num, chk_nums, prime_list)

# 하나씩 비교해서 넣는 경우
def solution(numbers):
    chk_nums = []		# 확인한 num 넣는 리스트
    prime_list = []
    answer = 0
    for i in numbers:
        if int(i) not in chk_nums:
            chk_nums.append(int(i))
            if chk_prime(int(i)):		# 소수인경우 prime_list에 추가
                prime_list.append(int(i))
        rem = numbers.replace(i, '', 1)		# i를 확인했다는 의미로 1번 빈칸 만들기
        search_numbers(rem, i, chk_nums, prime_list)
    answer = len(prime_list)
    return answer

 

📌다른사람의 문제풀이

1) 접근하려고 시도한 풀이

from itertools import permutations

def solution(n):
    a = set()
    
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))		# permutations 이용한 join 사용 -> map 이용하기
    a -= set(range(0, 2))	# 소수 아니라서 0,1 제외
    
    # 에라토스테네스체 사용
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
        
    return len(a)

2) 재귀문

primeSet = set()

# 소수인지 판별
def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

 
def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))
            
    # 리스트 숫자 모두 순회, 조합 만들어서 판단하기
    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])


def solution(numbers):
    makeCombinations("", numbers)

    answer = len(primeSet)

    return answer

 

📌리뷰

- 소수 판별하는거는 따로 함수 만들기