[프로그래머스/Level2] 소수 찾기

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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

[Python(파이썬)]

def solution(numbers):
    from itertools import permutations
    numbers = list(numbers)
    numlist, cnt, arr = [], 0, []
    for i in range(1, len(numbers)+1):
        numlist += list(permutations(numbers,i))
    for j in range(len(numlist)):
        numlist[j] = int(''.join(list(numlist[j])))
    numlist = sorted(list(set(numlist)))

    # 소수 구하기
    for l in range (numlist[-1]+1):
        arr.append(l)

    for k in range(2, len(arr)):
        for m in range(2*k, len(arr), k):
            arr[m] = False

    arr = list(set(arr))
    arr.remove(arr.index(1))
    arr.remove(arr.index(0))

    for n in numlist:
        if n in arr:
            cnt += 1

    return cnt

 

나의 풀이 2 - 에라토스테네스의 체 사용하지 않음(시간초과)

def solution(numbers):
    from itertools import permutations
    numbers = list(numbers)
    numlist, cnt = [], 0
    for i in range(1, len(numbers)+1):
        numlist += list(permutations(numbers,i))
    for j in range(len(numlist)):
        numlist[j] = int(''.join(list(numlist[j])))
    numlist = list(set(numlist))
    # 소수 구하기
    for k in range(len(numlist)):
        if numlist[k] in [0, 1]:
            numlist[k] = False
        else:
            for l in range(2, numlist[k]):
                if numlist[k] % l == 0:
                    numlist[k] = False

    return len(numlist)- numlist.count(False)

 

---

학습한 내용

# 학습할 다른 코드
from itertools import permutations
def solution(n):
    a = set()
    # 순열을 이용해서 모든 경우의 수를 구한다음 int형으로 변환
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    # a에서 {0,1} 차집합
    a -= set(range(0, 2))
    
    # 2 ~ max(a)의 제곱근 +1 까지
    for i in range(2, int(max(a) ** 0.5) + 1):
    
    # a에서 소수 아닌 수 차집합
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

• map(변환 함수, 순회 가능한 데이터) : 여러 개의 데이터를 한 번에 다른 형태로 변환

a |= set(map(int, map("".join, permutations(list(n), i + 1))))

순열을 사용할 때 for문을 두번 사용하며 전체를 다 구한 후 문자열 형태로 바꾸고 int로 바꿨는데 map()을 이용하여 한 번에 다른 형태로 변환 할 수 있음을 알았다. 

 

• 숫자 ** 0.5 사용하는 법

나의 풀이2 에서는 자기 자신과 1을 제외하고 모두 소수인지 판별하는 검사를 했다. 하지만 많은 시간이 소요되어 시간 초과가 떴는데 범위를 최고 숫자 -1 까지 검사하지 않고 제곱근까지 검사하면 단시간에 소수를 확인 할 수 있음을 알았다.  -> 에라토스테네스의 체

 

파이썬 제곱근 구하는 법 -> 숫자 ** 0.5 or math.sqrt를 사용

 

• set() :  중복된 데이터를 허용하지 않은 비순차, 가변 자료형 

[Python] 세트(set)

 

- set()의 합집합 차집합

 

합집합 :  '|' or union()

 

 차집합  :  '-' or difference()

a -= set(range(i * 2, max(a) + 1, i))

리스트를 이용하여 remove하지 않고 set을 이용하여 차집합을 이용하면 된다. 

 

---

문제 출처

 

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