파이썬으로 가장 작은 수를 만들어 첫 자리·끝자리 조합이 소수인지 확인하는 방법

문제 설명

숫자(0~9)로만 이루어진 배열 digits가 주어졌다고 가정해 보겠습니다. 이 문제에서 해야 할 일은 다음과 같습니다.

주어진 숫자들을 조합해 만들 수 있는 가장 작은 수를 찾습니다.
그 수의 첫 번째 자리 숫자와 마지막 자리 숫자를 조합해 만든 두 개의 두 자리 수가 소수인지 확인합니다.
생성된 수 자체와 소수 판별 결과를 출력합니다.

예를 들어 입력이 digits = [5, 2, 1, 7]이라면, 만들 수 있는 가장 작은 수는 1257입니다. 이때 첫 자리와 끝자리를 조합한 수는 17(첫 자리 1 + 끝자리 7)과 71(끝자리 7 + 첫 자리 1)이며, 두 수 모두 소수입니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

빈도수 계산: 각 숫자가 몇 번 등장하는지 저장하는 맵(digits_freq)을 생성합니다.
가장 작은 수 생성: 빈 문자열 number를 준비한 뒤, 0부터 9까지 순서대로 각 숫자를 빈도수만큼 반복해 이어 붙입니다. 작은 숫자부터 앞에 배치되므로 자연스럽게 가장 작은 수가 완성됩니다.
두 자리 수 만들기: 생성된 수의 첫 자리와 끝자리를 조합해 num(첫 자리+끝자리)과 rev(끝자리+첫 자리) 두 개의 수를 만듭니다.
소수 판별 후 반환:
- num과 rev가 모두 소수이면 → (number, num, rev) 반환
- num만 소수이면 → (number, num) 반환
- rev만 소수이면 → (number, rev) 반환
- 둘 다 소수가 아니면 → False 반환

예제 코드

from collections import defaultdict

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(arr):
    digits_freq = defaultdict(int)

    for i in range(len(arr)):
        digits_freq[arr[i]] += 1

    number = ""
    for i in range(0, 10):
        for j in range(digits_freq[i]):
            number += str(i)

    num = int(number[0] + number[-1])
    rev = int(number[-1] + number[0])

    if isPrime(num) and isPrime(rev):
        return int(number), num, rev
    elif isPrime(num):
        return number, num
    elif isPrime(rev):
        return number, rev
    else:
        return False

digits = [5,2,1,7]
print(solve(digits))

입력

[5,2,1,7]

출력

(1257, 17, 71)

코드 설명

isPrime() 함수는 2부터 num-1까지의 값으로 나누어 떨어지는 경우가 있는지 검사해 소수 여부를 판별합니다. solve() 함수는 먼저 defaultdict를 사용해 각 숫자의 등장 횟수를 세고, 0부터 9까지 순서대로 숫자를 이어 붙여 가장 작은 수를 만듭니다. 이후 첫 자리와 끝자리로 구성한 두 수의 소수 여부를 확인해 결과를 반환합니다.

참고: 배열에 0이 포함된 경우 가장 작은 수의 첫 자리가 0이 되어 의도하지 않은 결과가 나올 수 있습니다. 실제 응용에서는 0으로 시작하는 경우를 별도로 처리하는 로직을 추가하는 것이 좋습니다.