[코테] 99클럽 코테 스터디 10일차 TIL - 완전탐색

 

Question1 - [미들러] 소수 찾기

 

문제설명 https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

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

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

 

제한사항

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

 

---

 

 

문제풀이 

 

trial1

 

흩어진 종이조각이 적힌 문자열 numbers가 주어지고, 

numbers를 구성하고 있는 각 숫자들을 붙여 소수인 자연수를 몇개 만들 수 있는지 확인하는 함수를 구현해야 한다.

 

우선 생각했던 부분은 

1) 각 숫자들을 붙이는 조합을 만드는 방법이 필요하다는 점 

2) 그 조합들 중에서 소수를 판별하는 조건이 필요하다는 점이다.

두가지 측면에서 모두 완전탐색으로 '모든 경우의 수'를 확인해야 하는 듯 하다.

 

우선 1) 조합을 만드는 것은 itertools의 permutation을 활용했다. 

1부터 numbers의 개수 + 1까지 돌면서, 1개, 2개, 3개....등의 숫자를 조합한 조합을 만든다.

이때 이미 숫자들이 list로 분리되어 있기 때문에 permutation도 num_list중 몇개를 뽑아,

''.join으로 문자열을 합친 후, int 형태로 unique_numbers라는 셋에 추가하도록 한다.

 

이렇게 만든 unique_numbers라는 set의 모든 숫자들을 돌면서 소수인지 여부를 검토한다.

소수 여부를 검토할 때에는 1인 경우를 제외하고, 2부터 숫자의 0.5배 +1 인 반까지 돌면서 약수가 있는지 확인하면된다.

약수가 1과 자기자신밖에 없다면 소수로 판별, prime_numbers에 넣어준다.

import itertools

def solution(numbers):
    num_list = [i for i in numbers]  
    unique_numbers = set()
    
    for i in range(1, len(numbers) + 1):
        for permutation in itertools.permutations(num_list, i):
            num_str = ''.join(permutation)
            unique_numbers.add(int(num_str))

    prime_numbers = []
    for n in unique_numbers : 
        if n <= 1 : 
            continue
        else : 
            for i in range(2, int(n**0.5) + 1):
                if n % i == 0:
                    break
            else : 
                prime_numbers.append(n)

    return len(prime_numbers)

 

---

 

trial 2

 

앞선 방법과 크게 다르지 않으나, 소수 판별 조건을 따로 함수로 떼주면 더 직관적으로 표현할 수 있다.

소수라면 True, 아니라면 False를 반환하는 조건을 함수로 만들어, 추후 판별 조건으로만 추가해서 숫자를 추린다.

import itertools

def solution(numbers):
    def is_prime(n):
        if n <= 1:
            return False
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                return False
        return True

    num_list = [i for i in numbers]  
    unique_numbers = set()
    
    for i in range(1, len(numbers) + 1):
        for permutation in itertools.permutations(num_list, i):
            num_str = ''.join(permutation)
            unique_numbers.add(int(num_str))
    
    prime_numbers = [num for num in unique_numbers if is_prime(num)]
    
    return len(prime_numbers)