[프로그래머스] 소수 찾기/Python - Lv.2

❓문제

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

프로그래머스

성능 요약

코드 1 ➡️ 메모리: 280 MB, 시간: 860.28 ms

코드 2 ➡️ 메모리: 10.4 MB, 시간: 2639.75 ms

문제 설명

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

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

제한사항

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

입출력 예

numbers	return
"17"	3
"011"	2

✍🏻풀이

코드1 풀이
permutations를 이용하여 가능한 숫자의 조합을 찾는다.
0과 1을 집합에서 제거한다.
에라토스테네스의 체를 이용하여 소수가 아닌 수를 제거한다.

코드2 풀이
가능한 숫자의 조합을 모두 찾는다.
현재 숫자가 소수라면 집합에 넣는다.

💻코드

# permutations를 사용한 풀이
from itertools import permutations

def solution(numbers):
    nums = set()
    for i in range(len(numbers)): # 가능한 숫자 조합 찾기
        nums |= set(map(int, map("".join, permutations(list(numbers), i + 1))))
    nums -= set(range(0, 2)) # 0과 1을 제거
    for i in range(2, int(max(nums) ** 0.5) + 1): # 에라토스테네스의 체
        nums -= set(range(i * 2, max(nums)+ 1, i)) # i의 배수를 제거

    return len(nums)

# 백트래킹 같지 않은 백트래킹 풀이
nums = set()

def isprime(num):
    if num == 0 or num == 1:
        return False
    i = 2
    for i in range(2, num):
        if num % i == 0:
            return False

    return True

def backtracking(length, numbers, visit, num):
    if len(num) == length:
        if isprime(int(num)):
            nums.add(int(num))
        return

    for i in range(len(numbers)):
        if not visit[i]:
            visit[i] = True
            backtracking(length, numbers, visit, num + numbers[i])
            visit[i] = False

def solution(numbers):
    visit = [False] * len(numbers)

    for i in range(1, len(numbers) + 1):
        for j in range(len(numbers)):
            if not visit[j]:
                visit[j] = True
                backtracking(i, numbers, visit, numbers[j])
                visit[j] = False

    return len(nums)

💡새로 배운 내용

|= 연산자

• '|'는 or을 의미하므로 즉, union을 뜻한다.
• '|='은 현재 집합에 새로운 원소를 넣는다고 생각하면 된다.

숫자 ** 0.5 ➡️ 제곱근 표현

permutations 순열함수

• permutations(리스트, 선택할 원소 수)

combinations 조합함수

• combinations(리스트, 선택할 원소 수)

permutations, combinations함수 사용 시 itertools로부터 import해서 사용.

📍후기

전에 c++로 풀었을 때 permutatio 사용했는데 c++로 풀 때 permutation쓰면 시간 초과를 너무 겪었더니 permutations를 쓸 생각을 못 했다..