[CodingStudy] 완전 탐색 -소수 찾기

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

---

프로그래머스_완전 탐색 -소수 찾기

문제. 한자리 숫자가 적힌 문자열 배열 numbers가 주어졌을 때, 만들 수 있는 소수의 개수 return
( numbers는 0~9까지 숫자를 요소로 가지며 리스트의 길이는 1~7 )

 

ex) [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있으므로 2 return

---

import itertools

def solution(numbers):
    numlist=[]
    for s in range(1, len(numbers)+1): # 각 자리수 별로 순열값 생성해서 list에 추가
        numlist=numlist+list(map(''.join, itertools.permutations(numbers, s)))
        
    numlist=list(set(map(int,numlist)))   # 리스트 요소 중복 제거
    
    # 소수 판별
    count=0
    for num in numlist:
        flag=0 # 소수 인지 아닌지 판별을 위해        
        for i in range(2, num):
            if num%i==0 : # 소수가 아닌 경우
                flag=1
                break            
        if flag==0 and num!=0 and num!=1: # 소수인 경우
            count+=1
            
    return count

핵심은 itertools 라이브러리의 permutations 함수이다.

* permutations(순열을 만들 숫자가 담긴 리스트, 만들 순열의 자리수)

처음엔 만들 수 있는 모든 자리의 숫자를 for문 3개를 써서 만들었었다.

그런데 파이썬에는 permutations라는 순열 함수가 있었다!!

 

순열값이 AB라면 (A, B) 이런 형태로 만들어지기 때문에 join함수와 map함수를 써서 문자열로 만들어 list에 넣는다.

set함수를 써서 리스트 중복을 제거하고 각 리스트 요소가 문자열 타입이기 때문에 map함수를 한번 더 써서 int형으로 만든다.

* map(함수, 반복 가능한 자료형) > ex) map(int, alist)인 경우 alist내의 요소를 모두 int로 바꾸는데 map을 list로 한번 더 씌워주지 않으면 객체 위치만 반환되므로 주의! 

 

그 이후는 소수를 판별하는 코드이다.

0으로 나눠 떨어지면 소수가 아니므로 flag 변수에 표시를 하고 더이상 확인할 필요가 없기 때문에 break를 한다.

flag가 0이면 소수이고 0, 1은 소수가 아니므로 예외로 제외해 최종적으로 소수인 경우를 센다.

 

 

 

 

참고!

↓ permutations같이 효율적이고 편한 함수와 팁들이 많이 있어서 참고해서 공부하면 좋을 것 같다!

https://programmers.co.kr/learn/courses/4008

파이썬을 파이썬답게