99클럽 코테 스터디 23일차 TIL + 완전탐색

프로그래머스 소수찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

[입출력 예]

numbers	return
"17"	3
"011"	2

문제해석하기

• 입력값: 숫자로 이루어진 문자열 numbers (예: "17").
• 목표: 문자열로 만들 수 있는 모든 경우의 수 중 소수의 개수를 반환하기
• 제한 조건:
  • "011" 같은 숫자는 중복되지 않도록 처리하고,
  • 숫자의 순열을 활용해 가능한 모든 조합을 생성한다

1. 순열을 사용해 모든 조합 생성
   • 문자열로 주어진 숫자를 활용해 가능한 모든 조합을 만들어야 한다
   • Python의 itertools.permutations를 사용하면 효율적으로 해결할 수 있다
2. 소수 판별
   • 숫자가 소수인지 확인하려면 제곱근까지만 나눠도 충분하고,
   • 이를 일반화한 함수를 작성해 활용한다.
3. 중복 제거
   • 예를 들어, "011"에서 11이 여러 번 생성되지 않도록 set을 사용한다

from itertools import permutations

def is_prime(number):
    if number < 2:  # 소수는 2 이상의 자연수
        return False
    for i in range(2, int(number ** 0.5) + 1):  # 제곱근까지만 확인
        if number % i == 0:
            return False
    return True

def solution(numbers):
    possible_numbers = set()  

    for length in range(1, len(numbers) + 1):
        for perm in permutations(numbers, length):
            possible_numbers.add(int("".join(perm)))

    # 2. 소수 개수 세기
    prime_count = sum(1 for num in possible_numbers if is_prime(num))
    return prime_count

• itertools.permutations를 사용해 문자열로부터 가능한 모든 조합을 생성하고,
• int("".join(perm))로 문자열을 숫자로 변환해 set에 저장하면 중복 제거가 가능하다

1. 소수 판별 함수 is_prime
   • 입력값이 2보다 작으면 소수가 아니며, 2부터 제곱근까지 나눴을 때 나누어떨어지면 소수가 아니다
2. 소수 개수 계산
   • 생성된 숫자 조합 중 소수인 숫자의 개수를 sum으로 계산한다.

---

오늘의 회고

이 문제는 완전탐색의 전형적인 예제였다. 숫자 조합 생성(순열)과 소수 판별(효율적인 알고리즘)이 결합된 문제였고, 특히 Python의 itertools 라이브러리가 얼마나 중요하게 사용되는지 알 수 있었다. 다음에는 조합(combination)과 다른 탐색 방법에 대해서도 풀어보고 싶다.