프로그래머스 Level 2- 소수찾기(완전탐색)

# 문제 링크

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

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

# Strategy

1) 주어진 숫자를 모두 list에 추가한다
2) permutations 함수를 이용해서 리스트에 해당 숫자로 만들어지는 모든 순열을 문자열 형태로 저장한다.
3) 문자열을 int로 바꾼다.
-> 2,3 전략은 한 줄로 통합 가능하다.
4) 차후에 에라토스테네스의 체를 사용해서 소수를 판별하고, 소수로 판별된 숫자들은 011,11 이런 중복 케이스로 일어나는 문제를 방지하기 위해서 set으로 저장한다.
+) 나중에 안 사실이지만 애초에 2번을 수행할때 list말고 set으로 중복 케이스를 제거해주면 더 일이 준다.

 

# 제출 코드 1

from itertools import permutations 

def solution(numbers): 
    answer = 0 
    ansSet=set() 
    numList=[] 

    for i in range(len(numbers)): 
        numList.append(numbers[i]) 

    permList=[] 

    for i in range(len(numbers)): 
        permList+=list(map("".join,permutations(numList,i+1))) 

    newList=[int(p) for p in permList] 

    for item in newList: 
    	if item<2: continue; 
        
        check=True 
        for i in range(2,int(item**0.5)+1,1): #range 제곱근+1쓰는거 중요함 
          if item%i==0: 
            check=False 
            break 
          if check==True: 
              ansSet.add(item) 

     answer=len(ansSet) 
     return answer

 

# 기억해둘만한 IDEA

: Set을 통한 중복 제거, 에라토스테네스의 체, Map함수를 통한 정수 변환, join함수, 순열+조합 Library

1) 에라토스테네스의 체

: 소수를 판별할 때 사용할 수 있는 전략이다.
- 0,1은 기본적으로 소수가 아니므로 거르고 가며,
- 2보다 큰 수는 2~sqrt(n) 까지 나눴을때 나머지가 0인게 한개라도 있다면 소수가 아니다.

2) 리스트에 Map 사용하기

a=[1.2, 3.4, 5.6, 8.0] 
a=list(map(int,a)) 
#map을 통해 a에 저장된 수들을 int로 바꿔주고, 다시 리스트에 저장한다.

https://dojang.io/mod/page/view.php?id=2286

파이썬 코딩 도장: 22.6 리스트에 map 사용하기

 

3) join 함수: '구분자'.join(List)

: 리스트의 값과 값 사이에 구분자를 넣어서 문자열을 만들어 반환해준다
EX) ''.join(['a','b,'c'])="abc"

4) itertools library

: 재귀로 구현할수는 있으나, itertools가 10배는 빠르다고..ㅎ

from itertools import permutations
#combinations - 조합 
#combinations_with_replacement - 중복조합 

permutations(list,permutation_num)

 

# 코드 리팩토링

- 자 이제 코드를 깔끔하게 바꿔보자. 다른 분들의 풀이를 참고하여 고쳐보았다.

1) list comprehension 사용

-> 시간 복잡도의 변화는 모르겠고, 살짝 코드가 간결해지는 효과를 볼 수 있다.

for i in range(len(numbers)): numList.append(numbers[i]) 

#list comprehension으로 한 줄로 줄일 수 있다. 
numList=[numbers[i] for i in range(len(numbers))]

 

2) set으로 중복제거+ map 함수를 통해 코드 통합

#첫 코드에서 이 부분을 전체적으로 깔끔하게 바꿀 수 있다. 
permList=[] 

#애초에 permList를 set으로 바꿔서 중복을 다 제거해 놓으면 뒤에 소수 판별시 일이 좀 줄어든다. 
for i in range(len(numbers)): 
 	permList+=list(map("".join,permutations(numList,i+1))) 

newList=[int(p) for p in permList] 
#int로 바꾸는걸 map 함수를 한 번 더 사용함으로써 위의 for문에서 처리 가능 
#또 newList를 새로 정의하여 사용할 필요가 없어짐 

#깔끔하게 고친 결과 
permList=set() 
for i in range(len(numbers)): 
	permList|=set(map(int,map("".join,permutations(numList,i+1)))) 
    #|= intersection과 같은 뜻으로, set끼리 더할때 사용.

 

첫 코드에 비해서 두번째 코드가 set으로 중복만 제거해줘도 시간이 줄어드는 걸 확인 가능.

 

# 최종 코드

from itertools import permutations

def solution(numbers):
    answer = 0
    numList=[numbers[i] for i in range(len(numbers))]
    
    permList=set()  
    for i in range(len(numbers)):
        permList|=set(map(int,map("".join,permutations(numList,i+1))))
    
    ansSet=set()
    for item in permList:
        if item<2: #0,1은 소수 아님
            continue;
        check=True
        for i in range(2,int(item**0.5)+1,1):
            if item%i==0:
                check=False 
                break
        if check==True:
            ansSet.add(item)
                   
    answer=len(ansSet)            
    return answer