프로그래머스(LV2) - 소수찾기 파이썬(python)

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

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

소수 찾기

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

1. Set/Permutation을 활용한 Solution

from itertools import permutations


def solution(n):
    prime = set()
    # 1. 모든 숫자 조합을 만든다
    for i in range(len(n)):
        print("list(n) : " , list(n)) # n의 string을 하나씩 자른다.

        print("list(permutations(list(n), i + 1)) : " , list(permutations(list(n), i + 1)))
        # list(n)으로 부터 i+1개짜리 순열을 만들어 tuple로 반환한다
        # 순열이란 n개의 원소를 사용해서 순서를 정하여 r개의 배열로 나타내는 것을 말한다.
        # 순열은 순서가 있기 때문에 원소의 종류가 같아도 순서가 다르면 다른배열이 된다.

        print(list(map("".join, permutations(list(n), i + 1))))
        # map이란 반복가능한 객체에 각각 함수를 적용하고 싶을 때 사용하는 함수

        print(list(map(int, map("".join, permutations(list(n), i + 1)))))
        # int로 map함수 다시 사용하여 캐스팅

        prime |= set(map(int, map("".join, permutations(list(n), i + 1))))
        # 합집합들을 대입
        print(f'prime : {prime}')

    # 2. 소수가 아닌 수를 제외한다.
    prime -= set(range(0, 2))
    for i in range(2, int(max(prime) ** 0.5) + 1):
        prime -= set(range(i * 2, max(prime) + 1, i))
    return len(prime)


print(solution("17"))

1) 모든 숫자 조합을 만든다

• permutation / map / set라는 개념을 활용해서 모든 숫자 조합을 만들어 보자.
• permutation이란 "순열"을 의미하는 데, 쉽게 말해 모든 조합의 숫자를 만드는 것을 의미한다.
• combination(조합)과의 차이는, permutation은 다른 순서의 조합을 다른 조합이라고 여기고, combination은 같은 조합(중복)이라고 여긴다는 점이다.
  • 예를 들어, 대학교 수강신청을 할 때 1교시에 쉬운 과목, 2교시에 어려운 과목을 듣는 것과, 반대로 순서가 달라지는 것은 엄연히 다른 조합이니 permutation을 사용하는 것이 적합하다.
  • 하지만 블랙 잭이라는 게임을 할 때에는 9와 8이라는 카드를 받는 것과, 8과 9라는 카드를 받는 것은 결과적으로 같은 의미를 갖게되니 combination을 사용하는 것이 적합하다.
• permutation(list, count)
  • 첫 인자는 list 뿐만 아니라 반복 동작을 할 수 있는 dictionary 등의 객체가 전부 가능하다.
  • count는 "몇 개 줄까?"라는 질문에 답하는 것이다. 즉, count=2로 전달하게 되면 list에서 2개의 순열을 조합해달라는 의미가 된다.
• 즉 numbers라는 하나의 긴 String을, 각각의 숫자로 나누기 위해 list(numbers)로 변환한다.
• 이 리스트에서 numbers 개수만큼 뽑아서 숫자 조합을 작은 list들로 만든다.
• 여기에 map함수를 적용하여 list를 하나의 조합으로 합치고, int로 변환한다.
• 변환된 숫자를 집합으로 변환하여 set에 추가한다.

2) 소수가 아닌 수를 제거한다.

• 전체 숫자 조합을 만들었으니 소수가 아닌 수를 제거하면 된다.
• 0과 1은 소수가 아니라서 제거한다.
• 에라토스테네스의 체에 의하면 2부터 max(prime_set) ** 0.5 까지 의 배수만 확인하면 소수가 아닌 수를 전부 거를 수 있다.

https://tigre911.tistory.com/36

파이썬(Python) : set()

 

2. 재귀를 활용한 Solution

# 1. 결과물을 담고 있을 primeSet 정의
prime_set = set()

def isPrime(number):
    # 6. 0과 1은 False
    if number in (0, 1):
        return False

    # 7. 에라토스테네스의 체
    lim = int(number ** 0.5 + 1)
    for i in range(2, lim):
        if number % i == 0:
            return False

    return True


def makeCombinations(combination, others):
    # 5. 탈출 조건 / 비교 조건 : 지금까지 만들어진 조합을 
    if combination != "":
        if isPrime(int(combination)):
            prime_set.add(int(combination))
    
    # 4. 현재까지 만들어진 숫자에, 남아있는 숫자 중 하나를 붙여서 조합을 만든다
    for i in range(len(others)):
        makeCombinations(combination + others[i], others[:i] + others[i + 1:])


def solution(numbers):
    # 2. 모든 조합을 만드는 recursive 함수를 수행한다.
    makeCombinations("", numbers)

    # 3. primeSet의 length를 반환해준다.
    answer = len(prime_set)
    return answer

 

1) 전체 solution 풀이

• 재귀 함수로 모든 카드의 조합을 만들어본다.
• 만들어진 숫자는 combination에 만들어지니, combination이 소수인지 확인하고 prime_set에 추가한다.

2) 재귀함수를 통해 모든 숫자 조합을 만든다.

• 재귀함수를 사용해 모든 숫자 조합을 만든다.
• 재귀의 기본적인 동작은 현 combination + others의 i번째 character를 조합한다.

3) 현 combination이 prime인지 확인하고 prime_set에 추가한다.

• 에라토스테네스의 체란 2-MaxNum까지 전부 배수인지 확인할 필요가 없다는 것을 증명한 수학적인 이론이다.
• 예를 들어 97이라는 숫자가 소수인지 아닌지를 확인하고 싶다면, 97이 2~96 전부의 배수인지 확인할 필요가 없고,
• 2~sqrt(96)의 배수인지만 확인하면 된다는 이론이다. 
• 그렇기 때문에 우리도 isPrime 함수에서 전부를 보지 않고, sqrt한 값까지만 확인하고 비교한다.
• 이렇게 만들어진 prime_set이 정답을 전부 가지고 있으니, len(prime_set)이 소수의 개수가 된다.