[프로그래머스] Lv2 - 소수 찾기

문제

프로그래머스 코딩테스트 고득점 Kit - 완전탐색

• Lv 2. 소수 찾기 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/42839

코드 구현

from itertools import permutations

# 소수인지 판별하는 함수
def prime_check(num):
    if (num <= 1):
        return False
    for i in range(2, num // 2 + 1):
        if (num % i == 0):
            return False
    return True

def solution(numbers):
    answer = 0

    prime_list = set()      # 만들어진 소수를 담을 set (중복 제거를 위해)

    for i in range(1, len(numbers) + 1):
        per = list(set(permutations(numbers, i)))   # numbers 문자열에서 i개를 뽑아서 만들 수 있는 순열 생성 (set으로 감싸서 중복을 제거하고 -> list로 감싸서 접근에 용이하게 하기)

        # 해당 순열 리스트를 돌면서 숫자로 하나씩 만든 뒤 -> 소수인지 아닌지 판별하기
        for j in range(len(per)):
            make_num = ''

            for n in range(len(per[j])):
                make_num += per[j][n]               # 쪼개진 문자를 붙여서 하나의 숫자르 담은 문자열 만들기
            flag = prime_check(int(make_num))       # 소수인지 판별
            if (flag):      # 소수라면
                prime_list.add(int(make_num))       # set에 추가

    answer = len(prime_list)    # 정답은 prime_list에 담겨있는 소수들의 개수

    return answer

풀이

• permutations를 사용하여 모든 숫자 조합을 만들어서 소수인지 판별하였다.
• 우선 permutations에는 2개의 파라미터가 필요한데 하나는 순회할 요소, 하나는 개수이다.
  • permutations(순회요소, 뽑아낼 개수) → 뽑아내는 개수로 만들어지는 순열을 반환한다.
  • 각 숫자를 다른 요소로 봐서 만약 순회하는 요소 안에 같은 숫자가 들어있다면 중복이 생길 수 있다. 따라서 set() 으로 감싸서 중복을 제거하고, 다시 list() 로 감싸서 접근에 용이하게 해주어야 한다.
  • ex)

    numbers = “17”
    p = list(set(permutations(numbers, 2)))
    print(p)
    
    >>> [('1', '7'), ('7', '1')]

• 순열에서는 뽑아내는 개수에 따라서 조합해서 만들 수 있는 숫자가 달라지게 된다.
  그러나 이 문제에서는 1개의 요소로 만들 수 있는 숫자부터 numbers에 있는 길이만큼의 개수로 만들 수 있는 숫자를 다 파악해야하기 때문에 for문으로 permutations을 만들어준다.
  - ex) numbers = “123”이면, 아래와 같은 숫자들을 다 만든 뒤 소수인지 판단해야함

      1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
      

• 소수인지 판별하는 과정은 2부터 숫자의 절반 값까지 돌면서 나누어 떨어지는 수가 있다면 → 소수가 아님
  • prime_check() 함수로 소수인지 확인하고, 만약 소수라면 → set() 에 추가
    • 순열에서 중복을 걸렀다해도 ('0', '1', '1'), ('1', '1', '0') 같이 숫자로 만들었을 때 동일한 수가 만들어질 수 있기 때문
• 최종 답은 소수들을 담아둔 set()의 길이로 리턴한다.