[Programmers][완전탐색] 소수찾기 (211113)

코딩테스트 연습 - 소수 찾기

접근방법

• 노다가성이 짙은 풀이를 했다....
• 소수를 판별하는 함수를 활용했다.
• 주어진 문자열을 가지고 순열을 만들려고 했는데 자료형 등 고려할게 많아 생각보다 시간이 오래 걸렸다.
• 다른 분들의 좋은 풀이방법이 있어서 추가로 넣었다.

내 풀이

import math
from itertools import permutations

def isPrime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0:  # 2부터 시작하는 정수들로 나누어 떨어진다면 소수가 아니다
            return False
    else:
        return True  # 2부터 시작하는 정수들 모두 나누어 떨어지지 않으면 소수이다

def countIsPrime(numbers):
    cnt = 0
    visited = [0, 1]

    for i in range(1, 8):
        nums_for_num = list(permutations(numbers, i))
        perm_nums = []

        if nums_for_num:
            for tuple_num in nums_for_num:
                tt = ''
                for tn in tuple_num:
                    tt += tn
                perm_nums.append(int(tt))
            #print(perm_nums) #[1, 7] [17, 71] // [0, 1, 1] [1, 1, 10, 11, 10, 11] [11, 11, 101, 110, 101, 110]

            for perm_num in perm_nums:
                if isPrime(perm_num) and perm_num not in visited:
                    visited.append(perm_num)
                    cnt += 1

    return cnt

다른 풀이

• 내장함수만으로 풀었다. 문자열로 조합을 만드는 과정이 인상깊었다.

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