완전탐색 - 소수 찾기

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

프로그래머스

 

'소수 찾기' 문제는 프로그래머스에서 완전탐색 알고리즘 문제들 중 하나이다. 

완전탐색은 말 그대로 모든 경우를 확인해보고 답을 찾아내는 알고리즘을 완전탐색이라고 한다. 

이 문제에서 제한 사항 중에 input으로 들어오는 numbers의 길이가 최대 7까지인데, 이렇게 경우가 많지 않은(컴퓨터 입장에서)

상황에서 사용할 수 있는 알고리즘이다. 

 

이 문제를 읽고 나서 제일 처음 든 생각은, numbers의 숫자들로 만들 수 있는 모든 경우를 찾아내고, 그 경우들을 모두 소수인지 판별하면 되겠다고 생각했다. 

그리고 모든 경우를 찾는 방법으로는 파이썬 내장 tool인 itertools를 이용하면 되겠다고 생각했다. 

 

이전에 itertools의 combinations를 사용해 본적이 있는데, 보통 '파이썬 순열, 조합' 이라고 검색하면

itertools의 permutations와 combinations를 비교하는 글들을 많이 볼 수 있다. 

초반에는 combinations를 이용하면 되겠다고 생각했는데, 그렇지 않고 permutations를 이용해야 하는 문제이다.

왜냐하면 이 문제는는 순서를 고려해서 경우를 생각해야 하기 때문이다. 

 

예를 들어 [A, B, C]에서 2개씩 뽑는다고 하면,

permutations를 이용하면 [(A,B), (A,C), (B,C), (B,A), (C,B), (C,A)] 의 결과가 나오지만,

combinations를 이용하면 [(A,B), (A,C), (B,C)] 의 결과가 나온다. 

permutations는 순서를 고려하기 때문에 (A,B) 와 (B,A)가 다르다고 치지만, combinations는 순서를 고려하지 않기 때문에 두 개를 같다고 친다. 

 

'소수 찾기' 문제에서는 permutations를 이용하는게 적합하다. 

 

그 다음으로 고민했던 사항은, input의 numbers가 만약 '117'로 길이가 3 이라면, 

한 자리 숫자 순열, 두 자리 숫자 순열, 세 자리 숫자 순열 모두를 뽑아내야 하는데 permutations를 어떻게 이용할 것인가 이다. 

permutations는 인자를 두 개 받는데, 첫 번째 인자로는 iterable 한 객체를 받고 두 번째 인자로는 몇 개를 뽑아낼지의 숫자를 받는다. 

그럼 for 문을 통해 numbers의 길이를 가지고 permutations로 순열들을 뽑아내면 되는데, 

지금 생각하면 쉽게 떠올릴 수 있는 방법인데 문제를 풀 당시에는 시간이 좀 걸렸다. 🥲

 

이렇게 모든 순열들을 뽑아서 숫자들을 만든 다음, 그 숫자들을 각각 소수 판별 하기만 하면 된다. 

소수 판별하는 방법은 이전에 포스팅 한적 있는데, 에라토스테네스의 체 를 이용하면 된다. 

 

최종적으로 작성한 코드는 아래와 같다. 

from itertools import permutations

def check_decimal(num):
    if num == 0 or num == 1:
        return False
    m = int(num ** 0.5)
    for i in range(2, m+1):
        if num % i == 0:
            return False
    return True

def solution(numbers):
    numbers = list(numbers)
    answer = 0
    n = len(numbers)
    candidates = []

    for i in range(1, n+1):
        combo = list(permutations(numbers, i))
        for c in combo:
            c = ('').join(c)
            candidates.append(int(c))

    candidates = set(candidates)
    
    for candidate in candidates:
        if check_decimal(candidate):
            answer += 1
    return answer

소수 판별하는 로직은 check_decimal 이라는 함수로 분리했다. 

solution 함수 안에서 candidates 중복 제거 해주는 부분이 있는데, 같은 숫자는 굳이 여러번 소수 판별할 필요가 없다고 생각해서 중복 제거 처리 해주었다. 

 

이번 문제를 풀면서 itertools의 permutations를 처음 써봤는데, permutations와 combinations의 차이에 대해 좀 더 명확하게 

이해할 수 있었고, 앞으로 어떤 상황에서 무엇을 활용하면 좋을지 판단하는데 도움이 될것 같다.