[완전탐색] Level 2 소수찾기 - 파이썬

문제 설명

• 한자리 숫자가 적힌 종이 조각이 흩어져있습니다.
• 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
• 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

 

제한 사항

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

 

입출력 예시 및 설명

 

---

풀이)

먼저 내가 문제를 보자마자 필요하다고 생각한 로직은 2개이다

1. 소수 찾기 알고리즘
2. numbers로 만들 수 있는 모든 숫자의 조합 (단, 중복X)

 

풀이 방식은 간단하게 풀릴 것 같았는데 조합을 구현하는게 생각보다 어려웠다;;

먼저 소수 찾기 알고리즘은 간단했다

 

• 소수 찾기 : 만약 현재 수를 x라고 하면, x가 2부터 x-1까지의 수 중에서 나눠지는게 없으면 소수이다

그래서 이건 그냥 반복문으로 구현했고, 저기서 x가 0과 1인 경우에도 소수가 아니기 때문에 이 부분에 대해서도 예외처리를 해줘야 한다

 

그리고 모든 숫자의 조합은 itertools를 사용하였고, 중복 제거는 list -> set -> list 과정을 반복해서 구현했다

바로 아래의 코드를 보자

 

 

파이썬 코드)

import itertools

#소수 판별 함수
def is_prime_number(x):
    if x < 2: #0과 1은 소수가 아님
        return False
    
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

def solution(numbers):
    answer = 0
    combi = []
    str=""
    for j in range(1, len(numbers)+1): #모든 문자열 조합 찾기
        for i in itertools.permutations(numbers, j):
            combi.append(int("".join(list(i))))
            
    #리스트에서 중복 문자열 제거
    myset = set(combi)
    mylist = list(myset) 
    #print(mylist)
    
    for num in mylist:
        print(num)
        print(is_prime_number(num))
        if is_prime_number(num)==True:
            answer += 1
    
    return answer

permutation으로 모든 순열을 찾고 list에 넣는다

그리고 set과 list로 바꿔주면서 리스트의 중복 원소 제거 후 소수인지 확인!

조합 공부하느라 한 1시간 정도 푼 것 같다

빠잉!

 

---

스터디 중에 코드 개선이 되었다!

소수 찾기 알고리즘에서 원래는 2부터 x-1까지 검사를 해야 했는데, 이걸 루트 x까지만 검사해도 된다고 한다!

그래서 코드를 수정했다!!

 

수정된 코드)

import itertools
import math
# 소수 판별 함수
def is_prime_number(x):
    if x < 2:
        return False
    
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x) + 1)):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

def solution(numbers):
    answer = 0
    combi = []
    str=""
    for j in range(1, len(numbers)+1): #모든 문자열 조합 찾기
        for i in itertools.permutations(numbers, j):
            combi.append(int("".join(list(i))))
    
            
    #리스트에서 중복 문자열 제거
    myset = set(combi)
    mylist = list(myset) 
   # print(mylist)
    
    for num in mylist:
        #print(num)
        #print(is_prime_number(num))
        if is_prime_number(num)==True:
            answer += 1
    
    return answer