python 문제 풀이 복습 : [프로그래머스] 완전탐색 (1) 소수 찾기 (permutations 사용)

from itertools import permutations
def solution(numbers):
    
    # numbers의 조합을 통해 만들 수 있는 숫자를 저장할 리스트 
    answer = []
    
    # numbers의 길이를 n 으로 설정하고
    # 1자리부터 n자리 까지 모든 순열 permutations을 생성
    for i in range(1, len(numbers) + 1):
        # permutations(number, i) 는 numbers의 문자들을 i개씩 (i자리수) 뽑은 순열을 생성함
        for j in permutations(numbers, i):
            # ex) numbers 가 "17"이면 i = 1일때 ('1'), ('7')
            # i = 2일때, ('1', '7'), ('7', '1')가 생성됨
            # 생성된 튜플을 ''.join(j)로 문자열을 만들고, int로 숫자로 변형
            num = int(''.join(j))
            answer.append(num)
            
    # 소수 판별 알고리즘
    def is_prime(n):
        if n < 2 : # 0, 1은 소수가 아님
            return False
            
        else: 
            # n의 제곱근까지만 검사
            for i in range(2, int(n**0.5)+1):
                if n % i == 0:
                    return False # 나머지가 0이면 소수가 아님

        return True
                
    # answer의 중복 삭제
    answer = list(set(answer))
    print(answer)
    
    count = 0
    for k in answer:
        if is_prime(k):
            count += 1
    
    return count

코드 리뷰 (상세 설명)

1. 모듈 임포트 및 목표

   • from itertools import permutations
     • 이 구문은 itertools 모듈에서 permutations 함수를 가져옵니다.
     • permutations는 주어진 iterable(여기서는 문자열 numbers)에서 순서가 고려된 모든 가능한 순열(배열)을 생성해 줍니다.
   • 문제 목표:
     • 문자열 numbers에 있는 숫자 조각들을 조합하여 만들 수 있는 모든 정수를 구한 뒤, 그 중 소수(prime)가 몇 개인지 세어 반환합니다.

2. 후보 생성 단계

   • answer = []
     • 순열로 만들어진 숫자들 중 중복되는 값이 있을 수 있으므로, 빈 리스트 answer을 생성하고, 마지막에 set을 사용하여 중복을 제거합니다.
   • for i in range(1, len(numbers) + 1):
     • i는 조합에 사용할 자리수입니다.
     • 예를 들어, numbers의 길이가 2라면 i은 1과 2가 됩니다.
   • 내부 for 루프 (for perm in permutations(numbers, i):)
     • 각 i에 대해, numbers의 문자들을 i개씩 뽑은 순열을 생성합니다.
     • 예: numbers가 "17"일 때,
       • i=1 → 생성된 순열: ('1',)와 ('7',)
       • i=2 → 생성된 순열: ('1', '7')와 ('7', '1')
   • 문자열 결합 및 정수 변환
     • ''.join(j)으로 튜플에 담긴 문자들을 하나의 문자열로 연결합니다.
     • int(''.join(j))를 통해 문자열을 정수로 변환합니다.
     • 이렇게 생성된 숫자를 answer 리스트에 추가합니다.
     • 이 과정을 거치면 예를 들어, "17"으로부터 1, 7, 17, 71이라는 숫자들이 집합에 저장됩니다.

3. 소수 판별 함수 (is_prime)

   • 기본 조건 처리
     • if n < 2: return False
       • 0과 1은 소수가 아니므로 바로 False를 반환합니다.
   • 제곱근까지만 검사
     • for i in range(2, int(n ** 0.5) + 1):
       • 소수를 판별할 때는 n의 제곱근까지만 검사하면 충분합니다.
       • 예: n이 29라면, 2부터 int(√29)인 5까지 검사합니다.
   • 나누어 떨어지면 소수가 아님
     • 만약 n이 어떤 i로 나누어 떨어지면 return False 합니다.
   • 모든 검사 통과하면 소수
     • 루프를 다 돌고 나면, n은 소수이므로 return True 합니다.

4. 소수 개수 세기

   • count = 0으로 초기화한 후, answer 리스트에 있는 각 숫자에 대해 is_prime 함수를 호출합니다.
   • 소수인 경우 count를 1씩 증가시킵니다.
   • 마지막에 소수의 총 개수를 반환합니다.

5. 최종 반환

   • 함수는 최종적으로 소수의 개수를 반환합니다.

---

요약

• itertools.permutations를 사용하면, 문자열 numbers의 각 자리 숫자로 만들 수 있는 모든 순열(즉, 가능한 모든 숫자 조합)을 쉽게 생성할 수 있습니다.
• 중복 제거를 위해 집합(set)을 사용합니다.
• 소수 판별 함수는 간단한 제곱근 검사 방식을 사용하여 효율적으로 구현되었습니다.
• 마지막으로, 생성된 후보 중 소수인 숫자의 개수를 세어 반환합니다.

from itertools import permutations 란?

---

itertools.permutations는 Python의 내장 모듈인 itertools에 포함된 함수로,
주어진 iterable(반복 가능한 객체)의 모든 가능한 순열(permutaion)을 생성해 줍니다.
여기서 순열(permutation) 이란, 주어진 요소들을 순서에 따라 배열한 모든 경우를 의미합니다.

예를 들어, [1, 2, 3]이라는 리스트가 있을 때,
이들로 만들 수 있는 순열은 다음과 같습니다:

• 길이 3(전체 요소 사용):
  (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

• 만약 길이가 2인 순열을 원한다면,
  (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)
  와 같이, 2개씩 뽑은 모든 순서 있는 조합이 생성됩니다.

---

기본 문법

itertools.permutations의 기본 문법은 다음과 같습니다:

itertools.permutations(iterable, r=None)

• iterable: 순열을 만들고 싶은 대상(예: 리스트, 문자열 등)
• r: 선택적 매개변수로, 생성할 순열의 길이를 의미합니다.
  만약 생략하면 기본적으로 len(iterable)의 순열, 즉 모든 요소를 사용하는 순열을 생성합니다.

---

예시 1: 전체 순열 생성

from itertools import permutations

data = [1, 2, 3]
all_perms = list(permutations(data))
print(all_perms)

출력 결과:

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

• 여기서 permutations(data)는 [1, 2, 3]의 모든 3-순열을 생성합니다.
• 각 결과는 튜플 형태로 반환됩니다.

---

예시 2: 부분 순열 생성 (길이 r 지정)

from itertools import permutations

data = [1, 2, 3]
perm_2 = list(permutations(data, 2))
print(perm_2)

출력 결과:

[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

• 여기서는 r=2를 지정했으므로, 리스트 [1, 2, 3]에서 2개씩 뽑은 순열만 생성합니다.

---

itertools.permutations의 내부 동작 원리

1. 재귀 또는 백트래킹(Backtracking) 기반

   • 순열을 생성하는 과정은, 예를 들어 [1, 2, 3]의 전체 순열을 만드는 경우,
     • 첫 번째 위치에 올 수 있는 후보: 1, 2, 3 중 하나 선택
     • 만약 첫 번째 위치에 1을 선택하면, 남은 요소 [2, 3]에 대해 재귀적으로 순열 생성
     • 이 과정을 모든 후보에 대해 반복합니다.
   • 이와 같이 각 단계마다 선택하지 않은 요소들을 대상으로 순열을 만드는 백트래킹 기법을 내부적으로 사용합니다.

2. 최적화 및 C로 구현

   • itertools의 함수들은 C로 최적화되어 구현되어 있으므로, Python 코드로 직접 순열을 재귀 호출하는 것보다 매우 빠르고 메모리 효율적입니다.

---

활용 예시: 숫자 조합 문제

문제 상황:
문자열 "17"이 주어지면,
각 자리 숫자들을 이어 붙여 만들 수 있는 모든 정수를 구하고 싶을 때 사용할 수 있습니다.

from itertools import permutations

numbers = "17"
candidates = set()  # 중복을 제거하기 위해 set 사용

# 1자리부터 전체 길이까지 모든 순열 생성
for r in range(1, len(numbers) + 1):
    for perm in permutations(numbers, r):
        num = int(''.join(perm))
        candidates.add(num)

print(candidates)

출력 결과:

{1, 7, 17, 71}

• 여기서 permutations(numbers, r)를 사용하여 1자리, 2자리 순열을 각각 생성하고,
  ''.join(perm)로 튜플을 문자열로 바꾼 후, int()로 정수로 변환합니다.
• set을 사용해 중복되는 경우(예: "011" → 11)도 자연스럽게 제거됩니다.

---

결론

• itertools.permutations는 주어진 iterable에서 순서를 고려한 모든 가능한 순열을 생성해 주는 매우 강력한 도구입니다.
• 이 함수를 사용하면 재귀나 백트래킹 알고리즘을 직접 구현하지 않아도 되며, 코드가 훨씬 간결해집니다.
• 초보자도 간단한 문법과 몇 가지 예시를 통해 이해할 수 있는 도구이므로, 다양한 문제에서 순열 생성이 필요한 경우 적극 활용할 수 있습니다.