프로그래머스 | 소수찾기 문제 풀이

문제 접근 방식

숫자 카드를 조합하여 모든 경우의 수를 만들어 보고, 소수인지를 판단하는 문제 > 완전탐색 문제

 

[탐색 방식]

재귀를 활용한 방법과 순열을 활용한 방식 두가지를 떠올렸으며,

재귀 방식 시도 후, 순열을 활용한 방식을 선택

 

<순열 가짓수>

최대 경우의 수 = 7P1+ 7P2 + ... + 7P7  이다.

7P7 = 4640 이므로 최대 경우의 수는 10^4 정도 될 것으로 예상했고, 모든 경우의 수를 탐색하는 시간은 충분하다고 판단.

 

[소수 판별]

특정 수의 약수를 확인하는 방법과 에라토스테네스의 체를 이용한 방법 2가지가 있으며,

이 중 전자(약수를 통해 소수 판별)의 방식으로 진행

에라토스테네스의 체의 시간 복잡도  = O(n√n) 이고, 최대 숫자가 1e8 임을 감안했을 때 미리 구하는 것이

시간적으로 큰 장점이 없다고 판단했기 때문

 

[기타 사항]

수를 만들때 이전과 같은 수가 나올 수 있는데, 이 때마다 소수를 판별하는 것은 비효율적.

already_made라는 set을 두어서 같은 수에 대해 소수판별 하는 것을 방지

 

 

처리 방법

1. 만들려는 카드의 자릿수를 설정하고, 순열을 통해 숫자를 만든다.

2. 이전에 확인했던 수인지를 확인해서, 이미 진행했다면 pass 한다(소수인지 판단하는 시간을 줄이기 위함)

3. 처음 보는 수라면 소수인지 확인하고, 소수라면 prime_nums에 넣어주고, 그렇지 않다면 already_made에 넣어준다.

4. 소수의 개수를 반환한다.

 

코드

def isPrime(num):
    if num <=1:
        return False
    for i in range(2,num):
        if num%i==0:
            return False
    return True

def solution(numbers):
    numbers=list(numbers)
    already_made=set()
    prime_nums=set()
    for i in range(1,len(numbers)+1):
        for li in list(permutations(numbers,i)):
            num=int(''.join(li))
            if num in already_made:
                continue
            if isPrime(num):
                prime_nums.add(num)
            already_made.add(num)

    return len(prime_nums)

 

회고

시간 소요 - 38분,

예전 기억을 더듬어서 재귀함수 구현으로 풀려고 해봤는데

탈출 조건, 초기 설정 등 재귀 함수 구현에 미숙한 부분이 많아서 막힘 - 연습 필요