[프로그래머스 고득점 Kit] (완전 탐색) 소수 찾기

 

접근 방식

# 문자열 리스트로 쪼개기 -> list(string)

# 문자열 iteration-> 1, 17, .. 과 같은 방식 어떻게 처리하지? (permutations)

from itertools import permutations (s에 주목)

 

문자열의 개수만큼 n번 permutations를 수행하며 우리가 원하는 총 문자열 얻어야 -> 반복문 쓰기

 

#isPrime 함수 구현하는 데에서 실수 -> 0과 1을 처리 안해줘서 에러가 떴었음 : 이 문제는 디버깅하며 잡았다.

 

 

from itertools import permutations
def isPrime(num):
    if num ==1 or num==0:
        return False
    for i in range(2,num):
        if num%i==0 :
            return False
    return True
def solution(numbers):
    n = list(numbers)
    # print(n)
    ans = []
    for i in range(1,len(n)+1):
        a=list(permutations(n,i))
        for j in range(len(a)):
            if isPrime(int(('').join(a[j]))):
                ans.append(int(('').join(a[j])))
    # a = permutations(n,len(n))
    # print(('').join(list(a)[0]))
    # print(set(ans))
    answer = len(set(ans))
    return answer

 

아래는 깔끔한 다른 사람들 풀이

 

중복되는 수가 없게 or 연산을 수행하며 set을 늘려나가는 게 포인트

그리고 0부터 1까지 원소를 없애준다.

그리고 prime을 처리하기 위한 반복문을 바로 처리하는데, 2부터 전체 경우의 수 중 가장 큰 값의 루트 +1까지의 범위에서 반복하며 i의 2배부터 max(a)까지 iteration을 돌며 i의 배수를 삭제해주는 코드를 구성하셨다.

왜 가장 큰 값의 루트까지 값을 갖도록 하는지 이해할 수 있었다.

결국 가장 큰 값의 루트부터 계속 곱하다보면 가장 큰 값까지 제거할 수 있기 때문이다.

 

 

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))))
    a -= set(range(0, 2))
    # 가장 큰 값의 제곱근까지 순회
    for i in range(2, int(max(a) ** 0.5) + 1):
    	# i의 배수 제거
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)