[프로그래머스/코딩테스트 연습] 완전탐색 소수 찾기

이것도 어렵게 풀어낸 문제이다.. 어떻게 조합을 만들고, 여기서 또 소수를 찾을지 고민을 많이 했다... 

우선 이전에 다른 프로그래머스에서 소수를 판별하는 에라토스테네스의 체를 구현 해 둔 것이 있어서 그것을 이용하였다. 

에라토스테데스의 체로 구현한 소수 찾기 

소수를 판별해 내는 방법은 구현해 두었으니 이것을 이용해 수를 만드는 방법을 이용하였다.

여기서는 쓴 방법은 numbers 로 주어진 문자열에서 만들 수 있는 가장 큰 수 max를 만들고 max보다 작은 수 소수 i를 문자열 단위로 구성된 pn으로 나누고, pn을 구성하는 문자들이 num으로 구성할 수 있는 값인지를 확인하였다..

 

이렇게 쓴 과정으로 우선적으로 구현은 하여 두었지만, 다른 사람의 풀이를 보니 더 편한 방법이 있더라..

숫자 조합을 쉽게 python에서 구현하는 라이브러리가 있다. 

앞으로는 이 라이브러리를 써야지..

라이브러리는 itertools의 permutations이다. 

from itertools import permutations 

n = '011'
johab = []
for i in range(len(n)):
	johab.append(set(map(int,map(''.join,permutations(list(n),i))))

 

이런식으로 구현하면 가능한 모든 조합이 구해진다. 이를 이용하면 더 효율적으로 set간 비교를 통해 소수를 더 쉽게 찾을 수 있을 것이라고 생각한다. 

우선 permutations는 사용법만 적어둔다.