프로그래머스: 소수 찾기 (8 / 25)

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

코드

import itertools
import math

def solution(numbers):
    answer = 0
    parsed_list = [int(numbers[i]) for i in range(len(numbers))]

    # 1 parsed list를 가지고 조합할 수 있는 수를 만들기
    # itertools의 permutations를 사용하여 순열을 만든다.

    # 각 요소를 담을 순열 리스트 초기화
    permutations = []

    for i in range(1, len(parsed_list) + 1):  # 1자리 순열부터, list의 길이의 순열까지 모두 구하기 위함
        permutations.extend(itertools.permutations(parsed_list, i)) # - 이거 숙지하기

        # 순열을 숫자로 변환 - 이거 숙지하기
    nums = set(int(''.join(map(str, perm))) for perm in permutations)  # 중복이 있을 때는 set 자료형으로 변환한다.

    # 2 그 수가 소수인지 아닌지를 확인하는 로직 만들기
    for num in nums:
        if check_prime(num):
            answer += 1
    return answer

def check_prime(num):
    if num < 2:
        return False
    if num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

solution('011')

코드 풀이

1. answer를 0으로 초기화
2. 입력받은 string을 for 루프를 통해 list에 int로 담음 “011” → [0, 1, 1]
3. itertools의 permutaions를 사용하여 해당 리스트의 모든 요소의 순열을 구함
4. list.extend를 사용하여 요소들을 리스트에 추가함. append는 그 자체를 추가하는 것이므로 다름
5. 모든 순열 튜플을 반복하면서 set() 으로 자료구조를 변경해주어 중복을 제거한다.
6. 순열을 반복하며 해당 숫자가 소수인지 아닌지를 확인하는 로직을 가진다.
7. 소수인지 확인하는 로직
   • num < 2: 소수는 0과 1이 될 수 없다.
   • num == 2 or num == 3: 2와 3은 소수이다.
   • num % 2 == 0 or num % 3 == 0: 2의 배수와 3의 배수는 소수가 될 수 없다.

   for i in range(5, int(math.sqrt(num)) + 1, 2):
         if num % i == 0:
             return False
   return True
   
   숫자의 제곱근 이하의 수로 나누어 떨어진다면 그 수는 소수가 아니다.
   
   모든 조건에 걸리지 않는다면 그 수는 소수이다.

핵심 포인트

1. for 루프에서 range()를 사용할 때 start와 end를 정해준다면 end + 1을 반드시 해줘야 한다
   • 이것 때문에 한 번 틀림
2. 인풋으로 들어오는 string을 parse해서 각 요소를 리스트에 넣는다.
   • parsed_list = [int(numbers[i]) for i in range(len(numbers))]
3. parsed list를 가지고 조합할 수 있는 수를 만들기. 즉 순열을 만든다.
   • 순열: 주어진 요소들의 모든 가능한 순서를 고려한 배열이다.

   permutations = []
   for i in range(1, len(parsed_list) + 1):  # 1자리 순열부터, list의 길이의 순열까지 모두 구하기 위함
       # [1, 3, 2]
       permutations.extend(itertools.permutations(parsed_list, i)) # - 이거 숙지하기
   
       # 순열을 숫자로 변환 - 이거 숙지하기
   nums = set(int(''.join(map(str, perm))) for perm in permutations)  # 중복이 있을 때는 set 자료형으로 변환한다.

4. 해당 순열의 숫자들이 소수인지를 판별한다.

def check_prime(num):
    if num < 2:
        return False
    if num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

숫자 순열을 문자열로 변환 후 결합

import itertools

# 숫자 순열 생성
permutations = itertools.permutations([1, 2, 3], 2)  # (1, 2) (1, 3) (2 1) (2 3) (3 1) (3 3)

result = [''.join(map(str, perm)) for perm in permutations]

print(result)  # ['12', '13', '21', '23', '31', '32']

map(func, iterable): Iterable(리스트, 튜플 등) 내의 각 요소에 대해 func을 적용한 결과를 반환한다.

‘’.join(): Iterable내의 문자열들을 하나의 문자열로 결합한다. 앞의 빈 문자열(’’)은 각 요소 사이에 아무것도 넣지 않고 이어붙이겠다는 뜻