210530 완전/이진탐색 - 소수찾기

문제주소 : https://programmers.co.kr/learn/courses/30/lessons/42839

 

소수찾기 문제 쉬울줄 알았는데 어려웠다. 

numbers로 만들 수 있는 숫자의 조합을 만들기 위해 재귀함수를 만들어보려고 했으나 실패했다.

순열로 경우의 수를 만들려고 방법을 찾아보니 itertools라는 내장 모듈이 있어서 사용했다.

 

itertools를 이용해 모든 자리 수에 해당하는 순열을 만들고 set으로 중복을 제거했다.

이후 소수판별은 2부터 해당 숫자전까지 순서대로 나눠서 나머지가 생기면 소수가 아닌 것으로 판별했다.

 

import itertools as iter


def solution(numbers):
    answer = 0
    cases = set([])  # numbers로 만들 수 있는 모든 숫자의 조합을 저장할 set(중복 제거할려고 set 씀)


    # 순열을 이용해 모든 경우의 수를 만들어 set에 저장
    for i in range(len(numbers)):
        for j in list(map(''.join, iter.permutations(numbers, i + 1))):
            cases.add(int(j))

    # 소수판별 2와 3이상으로 구분
    for x in cases:
        if x == 2:
            answer += 1
        elif x > 2:
            check = 0

            # 나머지가 0이면 약수가 존재하므로 소수가 아니다
            for y in range(2, x):
                if x % y == 0:
                    check = 1
                    break

            if check == 0:
                answer += 1

    return answer

조금 더 보완하자면 for y in range(2, x) 부분을

for y in range(2, round(x ** 0.5) + 1)로 고치면 조금 더 빠르다.

 

설명은 못하겠는데 여튼 그렇다.