PROGRAMMERS 42839: 소수 찾기

Link : programmers.co.kr/learn/courses/30/lessons/42839

---

Python

counter = 0
memory = dict()
 
 
def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n in (2, 3):
        return True
 
    if n % 2 == 0 or n % 3 == 0:
        return False
 
    if n < 9:
        return True
 
    k, l = 5, n ** 0.5
    while k <= l:
        if n % k == 0 or n % (k + 2) == 0:
            return False
        k += 6
    return True
 
 
def BruteForce(numbers, arr, deapth, length):
    global memory
    global counter
    if arr is None:
        arr = [-1] * length
    if len(numbers) == 0:
        if int(''.join([str(i) for i in arr])) not in memory:
            memory[int(''.join([str(i) for i in arr]))] = 0
            if is_prime(int(''.join([str(i) for i in arr]))):
                counter += 1
            return
    for idx, val in enumerate(numbers):
        if deapth == length:
            if int(''.join([str(i) for i in arr])) not in memory:
                memory[int(''.join([str(i) for i in arr]))] = 0
                if is_prime(int(''.join([str(i) for i in arr]))):
                    counter += 1
            return
        else:
            arr[deapth] = val
            BruteForce(numbers[0:idx] + numbers[idx + 1:len(numbers)], arr, deapth + 1, length)
 
 
def solution(numbers):
    arr = [int(i) for i in numbers]
    for i in range(1, len(numbers) + 1):
        BruteForce(arr, None, 0, i)
    return counter
 
 
print(solution("011"))
 

FeedBack

1.  

---

 

 

 

cjw.git@gmail.com

https://53perc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0