[코딩테스트 고득점 Kit / Level2 🧒🏻 / 완전탐색] 소수찾기(python)

1. 문제 설명

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

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

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

2. 제한 사항

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

3. 입출력 예

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

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

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

4. 나의 풀이

이 문제는 문자열을 문자하나하나 나눈 다음, 가능한 조합을 구하고, 구한 조합들 중 소수의 개수를 세는 문제이다.

포인트는 조합을 구하는 것과 소수찾기의 효율 문제를 해결하는 것이다.

 

기존에는 아래와 같이 짰었다. 그랬더니 테스트케이스 2번과 10번이 시간초과가 발생해 통과하지 못했다.

왜일지 고민하다가 찾아보니 isPrime함수의 문제인듯 했다.

from itertools import permutations

def isPrime(num):
    count = 0
    if num <= 1:
        return False
    for i in range(2, num):
        if num %i == 0:
            count += 1    
    if count >= 1:
        return False
    return True
    

def solution(numbers):
    #문자열을 문자하나하나 나눈 다음, 가능한 조합을 구한다.
    #구한 조합들 중 소수의 개수를 센다.
    answer = 0
    datas = list()
    for i in range(1, len(numbers)+1):
        datas += list(map(''.join, permutations(list(numbers), i)))
    datas = set(datas)
    
    for data in datas:
        if data[0] == '0':
            continue
        if isPrime(int(data)):
            answer += 1
        
    return answer

내가 짠 것은 소수의 정의에 충실한 것이면서도, 무식하면서 강력한 것이었다...ㅋ

한 개의 소수를 구할 때는 그런대로 괜찮은 방법인데 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다.

소수를 구하기 위해 제곱근까지만 확인하는 방법을 사용하였더니 통과하였다..!

예를 들어 16이 2로 나누어떨어진다는 것은 8로도 나누어떨어진다는 것을 의미한다. 

 

5. 다른 사람의 풀이

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)

에라토스테네스 체를 사용해서 간결하게 푼 코드이다.

이 방법은 소수를 구하는 방법 중 가장 효율적이기로 유명하다.
찾고자 하는 수(n)까지 True로 채운 리스트를 생성한 후, 2를 제외한 2의 배수, 3을 제외한 3의 배수, 5를 제외한 5의 배수, ... sqrt(n)의 배수는 모두 False로 바꾼다. 결국 2~n까지의 숫자들 중 True인 숫자들이 소수가 된다.

 

def primeList(n):
	# 에라토스테네스의 체 초기화: n개의 요소를 True로 설정한다. (소수로 간주한다.)
    sieve = [True] * n
    
    # n의 최대 약수가 sqrt(n) 이하이므로 i = sqrt(n)까지 검사한다.
    m = int(n ** 0.5)
    for i in range(2, m+1):
    	if sieve[i] == True: #i가 소수인 경우
        	for j in range(i+i, n, i): #i이후의 i배수들을 False로 한다.
            	sieve[j] = False
    #소수목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

다시 돌아가면, a |= set(map(int, map("".join, permutations(list(n), i + 1)))) 에서 map함수안에 map을 넣어서 문자열을 한 번에 int형으로 바꾼뒤 set함수에 담아 중복을 없앤다.

set(range(0, 2))를 하면 {0, 1}이 나온다.

6. 깨달은점

아직 익숙하지는 않으나 map 함수가 편리할 것 같아 연습중이다.

어떻게 순열을 구할지 고민했는데 permutations라는 순열 모듈을 import해서 쓰니까 편리하다!

문자열을 list에 담으면 문자하나하나로 담긴다.

순열은 (2, 3)과 같은 형식으로 반환되는데 ''.join을 하면 구분자를 기준으로 합쳐진다. 그것들을 list에 담는다.

map안에 map을 넣을 수 있다.