[프로그래머스] Level2 | 소수찾기 - 파이썬(Python) | 완전탐색

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3 

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

프로그래머스에서 레벨1 연습문제인 소수찾기를 해 봤으니 완전 탐색을 이용한 레벨 2 소수찾기도 풀어보았다.

이 문제는 소수만 찾는게 아니라 주어진 문자열로 숫자 조합을 할 수 있어야했다.

---

숫자 조합을 할 수 있는 방법을 도무지 알 수가 없어서 구글링해서 itertools에서 permutations을 사용할 수 있다는 것을 알게 되었다. (permutations 참고한 사이트)

 

정답 풀이 코드

from itertools import permutations

#소수 판별 함수
def is_prime_number(x) :
    if x < 2 :
        return False
    
    for i in range(2, x) :
        if x % i == 0 :
            return False
            
    return True


def solution(numbers):
    answer = 0
    
    num = []
    for i in range(1, len(numbers)+1) :
        #순열 모듈 사용해서 나올 수 있는 모든 수 조합
        num.append(list(set(map(''.join, permutations(numbers, i)))))
    per = list(set(map(int, set(sum(num, [])))))
    
    for p in per :
        if is_prime_number(p) == True :
            answer += 1

    return answer

먼저 is_prime_number라는 소수인지 아닌지 판별해 주는 함수를 만들었다.

찾아보니까 이 함수는 꽤 유명하고 유용하게 쓰여서 고유명사처럼 함수이름을 저렇게 사용하는 것 같았다.

이는 소수 판별만 하기 때문에 for문을 사용하여 나누어 떨어지지 않으면 True를 반환하도록 한다.

 

permutations(iterable, r)을 사용하면 iterable의 요소들의 길이 r인 순열로 반환한다.

위의 코드에서는 모든 조합을 구하기 위해 for문을 사용하여 길이가 i로 바뀌도록 했다.

이때 line 21에서 num.append(list(set(map(''.join, permutations(numbers, i)))))을 print 하면 [['1', '7'], ['71', '17']]와 같은 결과가 나온다.

이렇게 나온 2중 리스트를 1차원으로 바꾸기 위해 sum을 사용했다.

sum은 sum(덧셈할 것, 처음에 더할 것)으로 사용할 수 있는데  처음에 더할 것을 빈 리스트 []를 넣어주면

sum(num, [])는 [] + [1,7] + [71, 17]이 되어서 리스트끼리의 덧셈으로 [1,7, 71, 17]이 된다.

이 때 나온 조합들에서 혹시 중복이 있을 수도 있기에 set을 사용했고 이를 num이라는 빈 리스트에 넣기 위해 다시 list로 바꾸었다.

 

이렇게 구한 문자열에서 나올 수 있는 숫자들의 조합을 구하고 나면 위에서 만들어 뒀던 소수판별 함수에 숫자들의 조합 리스트를 for문으로 반복하면서 소수일 때 answer에 1을 더해 소수가 몇개인지 구하였다.

 

 

굉장히 많은 사이트들을 찾아보았고 참고해서 겨우 풀었다.

레벨 1만 풀어보다가 레벨2를 푸니까 난이도가 급등한 것 같아서 내가 많이 부족하다는 것을 느꼈다 ㅎ...

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비