[Lv2.] 완전탐색 - 소수 찾기

👉 사용 언어 : PYTHON3

소수 찾기

✅ Solution

from itertools import permutations

def decimal_num(num):
    for i in range(int((num)**(1/2)) + 1):
        if i > 1 and num % i == 0:
            return 0
    return 1

def solution(numbers):
    res = []
    num_list = list(numbers)
    cnt = 0
    for i in range(1, len(numbers)+1):
        res.extend(permutations(num_list, i))
    for j in range(len(res)):
        res[j] = int(''.join(res[j]))
    res = set(res)
    for k in res:
        if k > 1 and decimal_num(k):
            cnt += 1
    return cnt

 

👉 문제 설명 및 제한 사항

• 매개변수 : 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers
  • 1 <= 길이 <= 7
  • 0 ~ 9 숫자만으로 구성
  • "013" > 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미❗ 
• 리턴값 : 종이 조각으로 만들 수 있는 소수의 개수
• 예시
  • numbers : "011"
  • return : 2
  • [0, 1 , 1] 로는 소수 [11, 101] 를 만들 수 있기 때문에❗ 
  • 11과 011은 같은 숫자로 취급

👉 아이디어

• 주어진 종이 조각의 숫자로 만들 수 있는 숫자 조합 으로 리스트 를 만든다.
  • permutations 을 사용하여 numbers 에 존재하는 숫자들로 만들 수 있는 모든 조합 을 구한다.
  • 구한 조합의 원소는 튜플 형태를 가지므로 join 함수 를 사용하여 문자열로 묶어준다.
  • 중복을 제거하기 위해 set 을 사용하여 조합으로 변환해준다.
• 소수인지 아닌지 판별하는 함수 decimal_num 을 따로 정의한다.
  • 가공 처리를 마친 res 집합 에서 반복문을 돌려 소수일 경우, 카운트변수 를 +1 한다.
• 카운트 변수를 리턴한다.

✅ 다른 사람 풀이 참고

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)

 

👉 깨달은 것 / 알게된 것

• 애초에 빈 조합을 정의한 후, 리스트의 튜플 원소를 map 함수 를 사용하여 문자열로 묶어준다.
• 또, map 함수 를 사용하여 문자열을 int 형으로 변환한다.
• set 을 사용하여 리스트를 조합으로 변환한 후, | 연산자로 합집합을 구한다.
• 에라토스테네스 체 방식을 통해 소수가 아닌 수는 a에서 제거한다.
• a의 길이값을 리턴한다.

✅ 집합

    : 순서x (= 인덱스로 접근 불가능 > TypeError 발생 > 반복문 을 통해 접근 가능)

    : 중복x

    : 요소 > 변경 불가능 한 자료형만 가능

✅ 집합 메서드

• add() : 단일 요소 추가
• update() : 여러 요소 추가 (리스트를 argument로 넘겨줄 수 있음)
• remove() : 특정 요소 제거 (제거하려는 요소가 집합에 없을 경우, KeyError 발생)
• discard() : 특정 요소 제거 (제거하려는 요소가 집합에 없어도, KeyError 발생x)
• pop() : 임의의 요소 제거
  • 맨 앞의 요소가 계속해서 제거되는 것을 확인할 수 있지만, 집합은 순서가 없기에 임의의 요소가 제거되는 것❗
• len() : 집합 요소 수 찾기
• clear() : 모든 요소 제거
• copy() : 집합의 얕은 복사본 만들기

✅ 집합 연산

• 합집합
  • union 메서도 : 집합1.union(집합2) > 집합1에 집합2 요소를 추가
  • | 연산자 : 집합1 | 집합2
• 교집합
  • intersection 메서드 : 집합1.intersection(집합2)
  • & 연산자 : 집합1 & 집합2
• 차집합
  • difference 메서드 : 집합1.difference(집합2) > 집합1에서 집합2 요소를 빼기
  • - 연산자 : 집합1 - 집합2
• 대칭 차집합
  • 공통 요소 제외한 모든 요소를 포함한 집합 (= 합집합 - 교집합)
  • symmetric_difference 메서드 : 집합1.symmetric_difference(집합2)
  • ^ 연산자 : 집합1 ^ 집합2

++ 참고 ++ 

frozenset() 을 사용하여 집합을 생성할 경우, 불변 집합을 생성하므로 위의 메서드를 사용하여 요소를 추가하거나 삭제할 수 없다. AttributeError 발생❗