[프로그래머스] 소수 찾기 (완전탐색 Lv. 2) - 파이썬 Python

0. 자세한 설명은 영상으로

 

1. 문제 설명 (출처 : 프로그래머스, 원 출처)

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

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

제한조건

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

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

• 예제 #1
  • [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
• 예제 #2
  • [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
  • 11과 011은 같은 숫자로 취급합니다.

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• 완전 탐색 유형은 가장 단순하고 그래서 참 쉽다.
• 하나도 빠짐없이 모든 경우의 수를 확인하고 있는지만 확인하면 된다.
• 이 문제의 경우에는 숫자 카드 7장으로 만들 수 있는 모든 숫자를 만들었는지를 첫 번째로 확인해야 하고
• 만든 모든 숫자가 소수인지 확인하면 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3-1. Set/Permutation을 활용한 Solution

from itertools import permutations
def solution(n):
    prime = set()
    # 1. 모든 숫자 조합을 만든다
    for i in range(len(n)):
        print("list(n)")
        print(list(n)) # n의 string을 하나씩 자른다.
        print("list(permutations(list(n), i + 1))")
        print(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("".join, permutations(list(n), i+1)))) # map이란 반복가능한 객체에 각각 함수를 적용하고 싶을 때 사용하는 함수                                                  
        print(list(map(int,map("".join, permutations(list(n), i+1))))) # map이란 반복가능한 객체에 각각 함수를 적용하고 싶을 때 사용하는 함수                                                  
        prime |= set(map(int, map("".join, permutations(list(n), i + 1))))
    # 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("117"))

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 까지 의 배수만 확인하면 소수가 아닌 수를 전부 거를 수 있다.

 

 

3-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)이 소수의 개수가 된다.

 

4. 참 쉽죠?

• 완전 탐색은 참 쉽다. 빠짐없이 모든 경우의 수를 다 따져보기만 하면 되는데, 컴퓨터는 이런 것을 하는 데 최적화되어있는 존재다.
• 이번 문제의 필자의 해결책이 최선은 아닐 것 같다. 사실 이렇게 정직하게 모든 경우를 확인해서 통과할 수 있을지 의심이 되기도 했지만, 1차 답안이라 생각하고 제출한 게 통과가 되어버렸다.
• 물론 실제 코딩 테스트에서는 최적화를 위해 고민하겠고, 훨씬 더 빠르고 간결한 답안이 많겠지만 완전 탐색은 완전 탐색답게 풀어봤다.
• 이렇게 단순한 생각/로직으로 작성한 코드는 가독성이 좋다는 정신승리로 이번 포스트는 마무리한다.