[프로그래머스][LV.2] 소수 찾기

[프로그래머스][LV.2] 소수 찾기 | python3

발자개a 2025. 3. 14. 19:25

문제설명

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

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

제한조건

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

문제풀이

permutations 의 조합 수를 변수로 두어 for문을 돌리면 전체 조합을 얻을 수 있다.

예를 들어 5개의 문자가 있고 이 문자들을 전체 조합을 알고 싶으면 permutations('문자열리스트',r) 의 r을 변수로 두어 1부터 5가지 돌아 전체 조합을 찾게 한다.

또한 소수를 판별하는 함수는 따로 빼어 코드를 간결하게 함.

나의코드

from itertools import permutations

def is_prime(n): # 소수 판별 함수
     
    if n<2: # 0과 1은 소수가 아니라서 빼줌
        return False
    
    for i in range(2, n//2+1):
        if n%i ==0:
            return False # 나누어지는 것이 있으면 소수가 아님
    return True

def solution(numbers):
    answer = 0
    p = [] # 조합된 숫자들 저장
    result = [] # 튜플 문자열로 바꾸기
    
    # 1부터 numbers의 길이 만큼 조합을 만들어냄
    for i in range(1, len(numbers)+1):
        p.extend(permutations(numbers,i)) # 조합들 전부 저장
        result = set([int(''.join(i)) for i in p]) 
        # 각 조합들마다 튜플로 저장되기 때문에 join을 사용해야함
        # ex) 2개의 조합 ('1','7') ('7','1') 이런식으로 나오기 때문에 join으로 합처줘야 '17','71' 이 나옴
        # int를 하므로써 011 => 11 로 변환
    
    for i in result:
        if is_prime(i): # 소수인지 아닌지 판별
            answer+=1
    
    return answer

참고하기

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

에라토스테네스 체를 이용한 풀이라고 한다.

에라토스테네스 체가 뭔지 몰라 찾아봣다.

에라토스테네스의 체란?

소수를 빠르게 찾는 알고리즘
특정 수 i의 배수를 제거하며 소수만 남기는 방식

✅ 원리

2부터 시작하여 남아 있는 숫자 중 가장 작은 수를 소수로 확정
그 수의 배수를 전부 제거
다음 남아 있는 숫자로 반복

예제 (1~20까지 소수 찾기)

숫자 상태

1	❌ (소수 아님)
2	✅ (소수)
4, 6, 8, ...	❌ (2의 배수 제거)
3	✅ (소수)
6, 9, 12, ...	❌ (3의 배수 제거)
5	✅ (소수)
10, 15, 20	❌ (5의 배수 제거)
...	...

✅ 남아 있는 숫자: {2, 3, 5, 7, 11, 13, 17, 19} (소수들)

📌 1. |= 연산자란?

a |= b 는 a = a | b 와 동일
집합(set)에서 합집합(Union) 연산을 수행
기존 집합 a에 새로운 요소들을 추가함

예제

a = {1, 2, 3}
b = {3, 4, 5}
a |= b  # a = a | b
print(a)  # {1, 2, 3, 4, 5}

**📌 2. range(i * 2, max(a) + 1, i)가 i의 배수를 제거하는 이유**

✅ range(start, stop, step) 동작 원리

start = i * 2 → i의 첫 번째 배수부터 시작
stop = max(a) + 1 → 최댓값까지 검사
step = i → i씩 증가하면서 배수를 찾음

예제 (a = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11})

1️⃣ i = 2일 때

range(4, 12, 2)  # {4, 6, 8, 10} 제거

🔹 남은 숫자 {2, 3, 5, 7, 9, 11}

2️⃣ i = 3일 때

range(6, 12, 3)  # {6, 9} 제거

🔹 남은 숫자 {2, 3, 5, 7, 11} (소수만 남음)

✅ 이렇게 i의 배수를 계속 제거하면 소수만 남는다!

📌 핵심 요약

✔ |= 는 집합의 합집합 연산자
✔ range(i * 2, max(a) + 1, i)는 i의 배수를 제거하는 코드
✔ 에라토스테네스의 체를 활용하면 소수를 빠르게 찾을 수 있음
✔ 모든 숫자 조합을 만든 후 소수 개수를 구하는 코드

import math
def check_prime(n):
    if n < 2:
        return False

    if n == 2:
        return True

    for i in range(2, int(math.sqrt(n)) + 1):
        if (n % i) == 0:
            return False

    return True

number_set = set()
def permutation(base, array):
    if base:
        number_set.add(int(base))

    for i, s in enumerate(array):
        permutation(base + s, array[:i] + array[i+1:])

def solution(numbers):
    answer = 0

    permutation("", list(numbers))

    answer = len(list(filter(check_prime, number_set)))

    return answer

재귀함수를 이용하여 푼 풀이...

아 난 재귀함수만 들어가면 이해를 못하겠다.

number_set = set()

def permutation(base, array):
    if base:
        number_set.add(int(base))  # 문자열을 정수로 변환하여 저장

    for i, s in enumerate(array):
        permutation(base + s, array[:i] + array[i+1:])  # 현재 선택한 숫자를 base에 추가하고 재귀 호출

✅ 이 함수가 하는 일

모든 순열(조합)을 생성
base가 비어 있지 않으면 number_set에 추가 (중복 제거)
array[:i] + array[i+1:]로 현재 선택한 숫자를 제외한 리스트를 만듦

📌 재귀 함수 permutation(base, array) 완전 정복!

이 함수의 역할은 문자열 numbers로 만들 수 있는 모든 숫자 조합을 생성하는 거야.

1️⃣ permutation(base, array) 코드 분석

def permutation(base, array):
    if base:
        number_set.add(int(base))  # 현재 만들어진 숫자를 저장 (중복 제거)

    for i, s in enumerate(array):  # array의 각 요소(숫자)에 대해 반복
        permutation(base + s, array[:i] + array[i+1:])  # 현재 숫자를 base에 추가하고, 남은 숫자로 재귀 호출

✅ 이 함수의 역할

현재까지 만든 숫자를 number_set에 저장
남은 숫자로 새로운 조합을 만들기 위해 재귀 호출
모든 가능한 숫자 조합을 생성

2️⃣ 예제 실행 (numbers = "17")

solution("17")

➡ numbers = "17"을 리스트로 변환하면 ['1', '7']

🔹 함수 호출 과정 (재귀 트리)

처음 호출: permutation("", ['1', '7'])
1을 선택 → "1" 남은 숫자 ['7']
7을 선택 → "17" 남은 숫자 [] (끝)
되돌아가서 7을 선택 → "7" 남은 숫자 ['1']
1을 선택 → "71" 남은 숫자 [] (끝)

3️⃣ 함수 호출 흐름 (자세한 과정)

처음 호출

permutation("", ['1', '7'])

base가 빈 문자열이라 저장 X
for 문에서 "1"과 "7"을 하나씩 선택

(1) "1"을 선택

permutation("1", ['7'])

"1"을 선택했으므로 "1"이 base로 들어감
남은 숫자는 ['7']

(2) "7"을 선택

permutation("17", [])

"7"을 추가하여 "17" 완성
남은 숫자가 없으므로 number_set.add(17) 저장
재귀 종료 후 이전 단계로 돌아감!

(3) "7"을 선택

permutation("7", ['1'])

"7"을 선택했으므로 "7"이 base로 들어감
남은 숫자는 ['1']

(4) "1"을 선택

permutation("71", [])

"1"을 추가하여 "71" 완성
남은 숫자가 없으므로 number_set.add(71) 저장
재귀 종료 후 이전 단계로 돌아감!

4️⃣ 최종적으로 저장된 숫자

number_set = {1, 7, 17, 71}

🔹 재귀 트리 형태

5️⃣ 재귀 종료 조건

array가 비어 있으면 더 이상 재귀 호출이 안 됨 → 함수 종료!
모든 숫자를 조합한 후, 이전 상태로 돌아가면서 새로운 조합을 생성

6️⃣ 요약

✔ permutation("", list(numbers)) → 모든 숫자 조합 생성
✔ base + s → 현재 선택한 숫자를 이어 붙이고 재귀 호출
✔ array[:i] + array[i+1:] → 선택한 숫자를 제외한 나머지로 새로운 조합 생성
✔ 재귀 호출이 끝나면 이전 상태로 돌아가서 다른 경우의 수를 탐색

🚀 이제 재귀 호출 과정이 명확하게 이해될 거야! 🚀