[프로그래머스] 완전탐색 - 소수찾기

🎯 programmers : 완전탐색 - 소수찾기

---

🤔 나의 풀이 1

📌 문제

- 프로그래머스 코딩테스트 연습 > 완전탐색 > Level 2 소수 찾기 

📌 날짜

2020.03.01

📌 시도 횟수

1 try

💡 itertools의 permutations 사용

from itertools import permutations

def solution(numbers):
    # 소수 구하기
    def isPrime(number):
        if number < 2:
            return False
        for i in range(2, number):
            if number % i == 0:
                return False
        return True

    # 간단 예외 처리
    if not numbers:
        return 0

    num_list = list(numbers)
    visited = set()
    answer = 0

    # 모든 가능한 조합 케이스 구하기
    cases = set()
    for i in range(len(numbers)):
        for x in permutations(num_list, i + 1):  # 자릿수가 i+1인 것에 대하여 순열 구하기
            cases.add(int("".join(map(str, x)))) # 구한 순열을 int로 형변환 해서 cases에 추가
	
    # 모든 cases를 각각 isPrime으로 검사 후 answer 개수 세기
    for n in cases:
        if isPrime(n):
            answer += 1
    return answer

💡 문제 해결 방법

- 주어진 숫자로 모든 가능한 숫자 조합을 만들기 위해 itertools의 permutation을
조금 변형해서 사용했다.
- permutation의 길이를 지정할 수 있음을 이용하여 모든 가능한 길이에 대해 순열을 구했다.
-------------------------------------------------------	
for i in range(len(numbers)):
        for x in permutations(num_list, i + 1):
        	cases.add(int("".join(map(str, x))))
-------------------------------------------------------	          
- 소수 판별을 isPrime 함수로 따로 빼서 소수인지를 검사했다.

💡 새롭게 알게 된 점

itertools.permutation(list, k)
- list에 대하여 길이가 k인 모든 가능한 순열을 리스트로 반환한다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 나의 풀이 2

💡 itertools의 permutations 사용

def solution(numbers):
    # 모든 케이스(case) 구하기
    def dfs(curr):
        num = "".join(map(str, path[:]))  # 현재 추가할 숫자는 path
        if num and int(num) not in cases:  # 공백인 경우는 제외하고
            cases.append(int(num))  # int로 변환 후 cases에 저장

        if len(curr) == 0:
            return

        for e in curr:
            next = curr[:]
            next.remove(e)

            path.append(e)
            dfs(next)
            path.pop()

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

    # 부분 집합 구하기
    nlist = list(numbers)
    cases = list()
    path = []
    dfs(nlist)

    # 소수가 몇 개인지 찾기
    answer = 0
    for num in cases:
        if isPrime(num):
            answer += 1
    return answer

💡 문제 해결 방법

- 이번에는 가능한 모든 숫자 조합을 구하기 위해 dfs를 이용했다.
- 예전에 '순열을 dfs로 구하기' 게시물을 참고하여 dfs 탐색 중에
현재 path가 처음 만들어진 숫자 조합이라면 cases에 추가하도록 했다.
- 나머지는 위의 코드와 동일하다.

💡 새롭게 알게 된 점

- dfs로 순열을 구현하는 방법을 복습할 수 있었다.
- 이해가 또 안된다면 이전 게시물을 참고하자.

😊 DFS로 순열 구하기

❌ (한번에 맞추지 못한 경우) 오답의 원인

-