programmers #소수찾기

Q. 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers     /        return

"17"	3
"011"	2

 

 

import copy

def permutation(lst, strum, numbers):
    for i in range(len(numbers)):
        cns = copy.deepcopy(numbers)
        add_strum = strum + cns.pop(i)
        lst.append(int(add_strum))
        permutation(lst, add_strum, cns)

def prime_list(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    if n <= 1:
        return False
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    #return [i for i in range(2, n) if sieve[i] == True]
    return sieve[-1]


def solution(numbers):
    num = []
    numbers = list(numbers)
    permutation(num, '', numbers)

    number_set = set(num)
    number_list = list(number_set)

    answer = 0
    for n in number_list:
        if prime_list(n):
            answer += 1
            print(n, answer)
    return answer

테스트 케이스 몇 개에서 시간초과로 실패가 떴다. 재귀함수가 디스크를 많이 잡아먹기도 하고 소수찾는 함수를 에라토스테네스 체를 사용해서 굴리는 시간이 많아가지고 그런 듯 하다. 그래서 제출은 squt이용해서 했고 개인적으로는 이 풀이가 더 마음에 들기때문에 이걸로 블로깅하겠다.

 

 

def prime_list(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    if n <= 1:
        return False
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    return sieve[-1]

에라토스테네스 체를 만들기 위해서 True로만 차있는 리스트를 하나 만들었다.

반복문을  n까지 다 돌릴 필요는 없어서 n의 루트까지만 반복을 하고 처음의 i는 그대로 True, 그 이후에는 i의 배수들을 False로 바꿔서 리스트에 저장하기로 한다.

 

def permutation(lst, strum, numbers):
    for i in range(len(numbers)):
        cns = copy.deepcopy(numbers)
        add_strum = strum + cns.pop(i)
        lst.append(int(add_strum))
        permutation(lst, add_strum, cns)

재귀함수...처음에 코드를 짰을 때는 deepcopy를 하지 않았더니 1,2,3을 연결할 때, 두 자리 수까지 밖에 되지 않아서 애를 먹었다. 결국 deepcopy를 써서 str 형태로 수들을 연결하고 int로 변환하여 다시 permutation에 넣게끔 연습했다.

 

 

def solution(numbers):
    num = []
    numbers = list(numbers)
    permutation(num, '', numbers)

    number_set = set(num)
    number_list = list(number_set)

    answer = 0
    for n in number_list:
        if prime_list(n):
            answer += 1
            print(n, answer)
    return answer

펄뮤테이션 함수를 쓰고 난 후에 담겨진 리스트들의 요소가 중복이 있을 수 있으니 set로 하여 중복을 제거하고 소수가 맞는지 확인하여 갯수를 리턴하였다.

 

다시 공부해야할 부분은 재귀함수(예제 많이 풀어보기)!!