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

문제 설명

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

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

제한사항

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

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

나의 풀이

import itertools

def solution(numbers):
    primeNuberlist =[]
    perList = []

    # 받은 문자열을 리스트로 변환 (함수를 따로 만들필요가 없었네)
    strToList = list(numbers)

    # 순열 만들기
    for i in range(len(strToList)):
        print(i+1)
        perList += list(itertools.permutations(strToList, i+1))

    # 소수인지 판별하기    
    for i in perList:
        temp = list(i)
        tempStr =""

        for j in range(len(temp)):
            tempStr += temp[j]

        if isPrimeNumber(int(tempStr)):
            primeNuberlist.append(int(tempStr))

    # 중복된 값을 없애기 위해 set으로 변환 후 다시 리스트로 변환함
    return len(list(set(primeNuberlist)))


# 소수인지 판별하는 함수
def isPrimeNumber(n):
    if n <= 1:
        return False
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i += 1

    return True

뭐 어떻게 풀긴했는데 다른 사람 코드를 보니 엄청 간결하고 쉽게들 푸셨더라. 나는 그래도 이 문제를 풀면서 set이랑 permutations나 알게되었고 조금은 성장함....

 

 

 

 

다른 사람의 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        print("처음: {}".format(map("".join, permutations(list(n), i + 1))))
        print("int map으로 감싼거: {}".format(map(int, map("".join, permutations(list(n), i + 1)))))
        print("set으로 바꾼거: {}".format(set(map(int, map("".join, permutations(list(n), i + 1))))))
                      
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
        print("a출력:{}\n".format(a))
        
    # 1은 제외
    a -= set(range(0, 2))
    print("차집합으로 뺀거 : {}".format(a))
    
    # int(max(a) ** 0.5) + 1 왜 이런식을 사용하는 걸까(범위를 제곱근 사용하는이유?)
    # 에라토스테네스의 체
    for i in range(2, int(max(a) ** 0.5) + 1):
        print("i : {}".format(i))
        # i의 배수를 제거하기
        a -= set(range(i * 2, max(a) + 1, i))
        print("a : {}".format(a))
        
    return len(a)

n = "17"
solution(n)

그냥 코드를 봐서는 모르겠어서 죄다 출력해서 눈으로 확인을 해봤다.

문자열이 17일 때

에라토스테네스의 체

소수란 1과 자기 자신만을 가지는 정수를 말한다. 에라토스테네스의 체라고 불리는 알고리즘을 사용하면 소수를 쉽게 구할 수 있다.

1. 1은 소수도, 합성수도 아닌 기초수이기 때문에 1을 제거한다.
2. 2는 소수이므로 2를 다른곳에 기록해둔다.
3. 자기 자신 (2)를 제외한 2의 배수를 모두 지운다.
4. 남아있는 수에서 2 다음 수인 3부터 진행을 시작한다.
5. 3은 소수이므로 2를 기록한곳에 기록한다.
6. 자기 자신(3)을 제외한 3의 배수를 모두 지운다.
7. 3의 다음 수는 4이지만 2의 배수로 2번에서 지워졌으니 남아있는 수 중 3의 다음 수인 5부터 진행을 시작한다.
8. 5는 소수이므로 2와 3을 기록한 곳에 기록한다.
9. 자기 자신을 제외한 5의 배수를 모두 지운다.
10. 위 과정을 끝까지 반복하면 구하는 구간의 모든 소수가 남는다.

에라토스테네스의 공식을 사용하면 모든 숫자를 다 검사할 필요없이 계산의 범위를 줄여 빠르게 구할 수 있다. 만약 120까지의 수 중 소수를 구한다하면 120까지 갈 필요없이 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 소수를 구할 수 있다. 그래서 식에서 루트를 사용하는 것이다.