알고리즘 풀이: [프로그래머스] 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/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은 같은 숫자로 취급합니다.

---

문제 풀이

주어진 numbers를 배치하여서 만든 숫자들이 소수인지를 판별합니다. 소수는 1과 자기 자신 외에는 어떠한 수로도 나누어지지 않습니다. 따라서 숫자가 소수인지를 판별하기 위해서는 숫자를 2부터 숫자의 제곱근까지 반복하여 나누면서 숫자가 나누어 떨어지는지 확인합니다. 나누어 떨어지면 숫자는 소수가 아닙니다.

 

 

numbers를 사용해서 가능한 모든 숫자를 만듭니다.

 

1부터 numbers의 길이의 개수만큼 numbers의 자릿수를 선택해서 순열을 구하는 과정을 반복합니다. 

 

순열로 가능한 숫자 찾기

17에 대해서 한 자릿수로 만들 수 있은 순열은 1과 7이 있습니다. 그리고 두 자릿수로 만들 수 있는 순열은 17과 71이 있습니다. 따라서 17로 만들 수 있는 수 1, 7, 17, 71이 소수 판별의 대상이 됩니다.

 

011에 대해서 한 자릿수로 만들 수 있는 순열은 0, 1, 1이 있습니다. 이러한 방식으로 두 자릿수인 경우와 세 자릿수인 경우를 모두 구합니다. 최종적으로 중복을 제거하고 0이 아닌 0으로 시작하는 숫자(01, 011)를 제거하면 0, 1, 10, 11, 101, 110이 소수 판별의 대상이 됩니다.

 

 

숫자가 소수인지 판별하기

 

소수는 1과 자기 자신으로만 나누어 떨어질 수 있습니다. 따라서 소수를 판별하기 위해서 숫자를 2부터 숫자의 제곱근까지 반복하여서 나누어 떨어지는지 확인합니다.

 

어떠한 숫자가 (숫자의 제곱근 + 1)로 나누어 떨어지면 몫으로 나온 결과는 숫자의 제곱근 보다 작을 것입니다. 이는 (숫자의 제곱근 + 1)로 나누어 떨어지는지 판별하는 것과 (숫자의 제곱근보다 작은 수)로 나누어 떨어지는지 판별하는 것이 동일하다는 것을 의미합니다. 따라서 효율성을 위해 숫자의 제곱근까지만 반복해서 나누어 떨어지는지 판별합니다.

 

소스 코드

순열을 사용해서 가능한 모든 숫자 찾는 함수

from itertools import permutations


def find_candidates(numbers):
    # numbers 의 자릿수 length
    length = len(numbers)

    # set 자료구조는 중복을 허용하지 않는다.
    candidates = set()

    # 한 자릿수부터 N 자릿수까지 가능한 모든 순열 파악하기
    for n in range(1, length + 1):
        # permutations() 는 리스트의 원소에 대해서 n 개의 순열을 구해준다.
        # ''로 묶은 이후에 int 로 형변환하여서 0이 아니면서 0으로 시작하는 숫자를 제거한다
        for candidate in map(lambda x: int(''.join(x)), permutations(numbers, n)):
            candidates.add(candidate)

    return candidates

소수 판별 함수

def determine_prime(number):
    # 0과 1은 소수가 아니다
    if number in [0, 1]:
        return False

    # 2부터 숫자의 제곱근까지 반복하여서 나누어떨어지는지 확인
    for n in range(2, int(number ** 0.5) + 1):
        # 나누어떨어지므로 소수가 아니다
        if number % n == 0:
            return False
    return True

메인 솔루션 함수

def solution(numbers):
    # 각 자리수의 리스트로 만들기
    numbers = [num for num in numbers]

    candidates = find_candidates(numbers)

    counter = 0
    for candidate in candidates:
        counter += int(determine_prime(candidate))

    return counter

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/%EC%86%8C%EC%88%98%20%EC%B0%BE%EA%B8%B0.py

dhsong95/-PRACTICE-Programmers-Algorithm