[파이썬] 소수 찾기

programmers.co.kr/learn/courses/30/lessons/42839

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

문제 설명

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

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

 

제한사항

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

입출력 예

numbers	return
17	3
011	2

 

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

🤔 메타인지

1. 소수인지 판정

어떻게 판정하지.. 소수는 1제외, 2의 배수 제외(2 빼고), 3의 배수 제외(3뻬고), 5의 배수 제외(5빼고), 7의 배수 제외(7빼고), 11의 배수 제외(11빼고), 13의 배수 제외(13빼고), 17의 배수 제외(17빼고), 19의 배수 제외(19빼고)

이렇게 하면 너무 많은데...

중간까지만 볼까... 수를 나누는 것을 

 

2. 순열을 만든다. but int로 변환해야 하고...

 

3. permutations를 쓰면 [()] 튜플이다.

 

순열은 만들었다. 오름차순 정렬한 다음에 앞 글자가 0이면 뺄까

아니면 애초에 0이 앞에 못오도록 할까

순열을 다 만든 다음에 소수인지 판정해볼까

최대한 중복을 없애고 함수 호출하는게 좋을 듯.

 

💗 나의 풀이

 

from itertools import permutations

def solution(n):
    answer=[]
    def check(ans):     # 소수 판정
        numbers=[]
        for i in ans:
            num=int(i)      # 문자열을 int로 변환
            if num<=1 :		# num이 0또는 1이라면
                continue
            for j in range(2, num//2+1):
                if num%j == 0:
                    break
            else:
                numbers.append(i)
        return numbers
                       
    for i in range(1, len(n)+1):        # n의 길이만큼 반복하며 순열만들기
        answer+=set(list(map(''.join,permutations(n, i))))  # 순열
    re=check(answer)					# 소수인지 검사하는 함수 호출
    re=list(set(map(int, re)))  # int로 변환하고 중복제거
    return len(re)

 

solution 함수에서 for문은 순열을 만든다.

순열을 이용했다. 순열과 조합의 차이는 알긴 아는데 제대로 이해가 덜 된 것 같다. 언제 사용해야 하는지가 잘 모르겠다. 이 문제가 조합인 줄 알았다가 순열 사용함ㅋ

check함수는 소수인지 판정하는 함수이다. 반복문을 쓰면서 ans 안의 값들을 검사한다. i가 문자열이기 때문에 int로 변환해서 num에 담았다. 이 값이 0또는 1이라면 소수인지 확인할 필요도 없으므로 continue를 써서 밑에 코드가 실행되지 않도록 했다. 두번째 for문에서는 2부터 num의 절반만큼 반복하면서 num을 나눈다. 나머지가 0이 한 번이라도 나오면 소수가 아니다. for-else문을 사용해서 for문내에서 break가 한 번도 발생하지 않았다면 numbers에 i를 추가했다. 

리스트 re 안의 값들을 int로 변환(map 이용)하고 set을 통해 중복제거함.

 

# 다듬은 코드
from itertools import permutations

def solution(n):
    answer=[]
    def check(ans):     # 소수 판정
        numbers=[]
        for i in ans:
            num=int(i)      # 문자열을 int로 변환
            if num<=1 :
                continue
            for j in range(2, num//2+1):
                if num%j == 0:
                    break
            else:
                numbers.append(num)
        return numbers
                       
    for i in range(1, len(n)+1):        # n의 길이만큼 반복하며 순열만들기
        answer+=set(list(map(''.join,permutations(n, i))))  # 순열
    re=check(answer)
    re=set(re)     # int로 변환하고 중복제거
    return len(re)

 

💗 다른 사람 풀이

 

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)

 

순열을 만들고 문자열을 int로 변환 후에 set으로 중복을 거름. set 연산에서 |는 합집합 연산이다. a가 set이기 때문에 |=를 써야하지 +=쓰면 안 통한다.

a에서 0부터 1까지 뺀다.(차집합) 나는 if조건으로 확인하고 continue를 썼었음. 

2부터 a의 최댓값에 0.5를 제곱한 값을 정수화한 수까지 반복한다. 에라토스테네스의 체를 썼다. a의 최대 약수가 sqrt(a) 이하이므로 sqrt(a)까지 검사. 2의 배수부터 i만큼 증가하면서 a에서 해당하는 숫자를 뺀다. range의 i*2부터 시작해서 max(a)+1까지 i만큼 증가하면서 뺀다고 착각했다. 디버그 해보니 a에서 삭제할 범위를 지정해 놓은 것이다. range에서 끝 i를 빼면 ValueError: max() arg is an empty sequence가 뜬다.

차집합에서 range가 이해안됨. 왜 i*2부터냐 2의 배수도 아니고, max(a)+1은 알겠는데 끝이 왜 i냐.

-> i를 제외한 i의 배수를 a에서 없앤다. i만큼 증가하는 것=배수

내 코드와 비교해보았다. 입력값이 "17"일 때 순열이 똑같음. 하지만 "011"은 다음과 같이 차이가 난다. 나는 문자열로 만들어서 set을 쓰더라도 '01'은 '1'은 다른 숫자로 인식된다. 

다른 사람 풀이 = {0, 1, 101, 10, 11, 110} 내가 짠 소스 코드 = ['0', '1', '11', '01', '10', '011', '110', '101']

check함수에서 int함수를 쓰고 있는데 순열 만들 때 했으면 좋았을 것이다. 

 

# 바꾼 내 코드
answer+=set(map(int,(map(''.join, permutations(n, i)))))  # 순열