[Python] 프로그래머스 lv.1 소수 찾기

 

문제 분석

• 한자리 숫자가 적힌 종이 조각이 있다.
• 종이 조각을 붙여 만들 수 있는 소수의 개수 return

 

코드 설계

• 순서 있고, 중복x
• 순열
• 데이터의 갯수만큼 모든 순열 조합을 찾고
• 그 중 소수인 수 구하기

• 모든 숫자 조합 찾기

from itertools import permutations

arr = [1,2,3]
for r in range(1, len(arr)+1):
    for i in permutations(arr, r) :
        num = ''
        for j in i :
            num += str(j)
        print(int(num))
        
        
# result
1
2
3
12
13
21
23
31
32
123
132
213
231
312
321

 

정답 코드

1차 코드 - 실패 : 기대값과 출력값이 다름

from itertools import permutations

def isPrime(n) :
    if n < 2: 
        return False
    for i in range(2, n//2+1):
        if n % i == 0 :
            return False
    return True

def solution(numbers):
    answer = 0
    num_arr = []

    # 종이 조각 문자열을 배열로 바꾸고
    for n in numbers :
        num_arr.append(n)

    # 가능한 모든 숫자 찾고
    for r in range(1, len(num_arr)+1):
        for i in permutations(num_arr, r) :
            num = ''
            for j in i :
                num += str(j)
            if isPrime(int(num)) : # 소수이면
                answer += 1
    return answer

n = "011"
print(solution(n))

중복 검사를 안함

 

2차 코드

from itertools import permutations

def isPrime(n) : # 뭔가 더 효율적으로 쓸 수 있을거같은데
    if n < 2: 
        return False
    for i in range(2, n//2+1):
        if n % i == 0 :
            return False
    return True

def solution(numbers):
    answer = 0
    num_arr = []

    # 종이 조각 문자열을 배열로 바꾸고
    for n in numbers :
        num_arr.append(n)

    # 가능한 모든 숫자 찾고
    before = []
    for r in range(1, len(num_arr)+1):
        for i in permutations(num_arr, r) :
            num = ''
            for j in i :
                num += str(j)
            if int(num) in before : # 중복 체크
                continue
            before.append(int(num))
            if isPrime(int(num)) : # 소수이면
                answer += 1
    return answer

 

다른 사람 코드 1

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):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

다른 사람 코드 2 - 재귀

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