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

문제 설명

제일 먼저 생각난 것은 itertools의 combinations입니다. 하지만 이는 순서를 고려하지 않기 때문에, 순서가 바뀌면 숫자가 바뀌는 문제에는 적절하지 않아, 이후 permutations을 생각하였습니다. 또한 이는 같은 숫자가 나올 경우에는 중복이 되기 때문에 count를 해야하는 문제의 특성상 중복제거를 해야합니다.  이 아이디어를 가지고 문제 풀이를 해보면,,

 

 

우선 numbers를 list로 변환하여, 붙어있는 문자열을 숫자마다의 list로 바꿔줍니다.

이후 소수 판단할 후보 숫자들을 넣을 total list를 선언하고, for문을 돌려 최소 1개에서 문자열의 개수만큼까지 순열을 뽑아줍니다. 뽑은 숫자들을 ''.join()을 이용해 문자열로 바뀌주고, 이후 int 함수를 이용해서 숫자로 바꿔줍니다.

int를 사용하면 011와 같은 문자열을 11과 같은 정수로 변환할 수 있습니다.

 

이후 list(set())을 통해 중복되지 않는 리스트로 변환한뒤, 소수 판별 함수에 넣어 소수 개수를 카운트하면 됩니다.

 

저는 제일 간단한 소수 판별 함수를 작성하였는데, 에라토스테네스 체라는 알고리즘도 있더라고요, 한 번 찾아 봐야겠습니다.