99클럽 코테 스터디 10일차 TIL + 프로그래머스/2/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은 같은 숫자로 취급합니다.  (set 이용)

 

 

<코드>

from math import sqrt
# 조합대신 순열로 (순서가 중요)
# from itertools import combinations
from itertools import permutations

def is_prime_number(n):
    if n <= 1:
        return False
    # 2부터 시작해야함
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False;
    return True;

def solution(numbers):
    number_set = set() # set으로 중복 해결함
    
    for length in range(1, len(numbers) + 1):
        for perm in permutations(numbers,length):
            num = int(''.join(perm)) # 튜플을 하나의 문자열로 합친 뒤 숫자로 변형
            number_set.add(num)
    
    prime_count = sum(1 for num in number_set
                     if is_prime_number(num))
    
    return prime_count
            
        

# def solution(numbers):
#     count = 0
#     numbers_list = list(numbers)
#     for i in range(1 ,len(numbers_list) + 1):
#         for com in combinations(numbers_list, i):
            
#             new_com = int (list(com))
#             # com_list = list(com)
#             # for v in com_list:
#             if is_prime_number(new_com):
#                 count += 1
    
#     return count               


# 소수 판별에 3가지 방법
# I-1. 나누어 떨어지는것 하나라도 있으면 O(N)
# I-2. 절반만 검사하기
# I-3. 제곱근 -> 대칭된다는 점

# II-1

- 중복을 방지 혹은 같은것으로 취급하는 조건이 있는 경우에는 set 사용이 좋음

 

- 리스트, 튜플은 .join(perm) 으로 해결 가능

 

- 모든 판별을 해서 그 갯수를 구하는 방식은 매번 연산할 필요없이 임시적으로 list나 set 변수에 넣어둔다

그러고 추후에 꺼내서 하나씩 판별하는 방식도 충분히 고려할 수있음

 

- 그러고 그 prime_number 구하는 변수는 리스트 컴프리헨션 방식으로 count 를 1씩 더해가는 방법이고

sum() 을 이용해서 순차적으로 연산함

 

- 

 

<모범사례>

 

 

 

<배운점>

1. 순열 조합

순서가 중요하면 순열, 중요하지 않으면 조합

ex: 순서가 중요한경우

1,2 / 2,1 의 의미가 서로 다른경우

두개가 같으면 조합!

 

2. 소수 찾기

방법은 3가지 

전체 탐색 / 절반만 검사하기 / 제곱근