문제 링크
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 해설
종이조각에 각각 한자리 숫자가 적혀있고, 주어진 숫자를 조합해서 총 만들 수 있는 소수가 몇 개인지 찾는 문제이다.
처음으로 든 생각은 "오... 소수 정의가 정확히 어떻게 되더라.. 소수가 뭐였지?" 였다.^^ 그래서 정확한 정의를 찾아봤다.
소수(Prime Number)란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수.
위의 정의를 생각해보고, 다음과 같은 생각이 이어졌다.
"주어진 숫자로 만들수 있는 모든 조합을 생성한 후, 소수를 판별하는 함수를 통해 소수의 개수를 리턴하면 되겠다!"
우선적으로 itertools모듈에서 순열을 사용하기위해 permutations함수를 가져왔다.
주어진 숫자로 가능한 모든 조합을 생성하는 get_combinations함수를 만들어주고 결과를 combinations에 담는다.
만들어진 combinations의 중복 조합을 제거하기위해(중복된 조합을 제거함으로써 동일한 순열에 대해 중복작업을 피할수 있다.) set(combinations)을 해준다. 그러고 나서, 소수인지 아닌지 확인하는 is_prime 함수를 if절을 통해 소수이면 prime_count를 +1 해준다.
핵심 로직인 소수를 판별하는 is_prime함수이다. 소수의 정의는 2보다 큰 자연수라고 했으니 만약 2보다 작다면 false를 리턴해준다.
그 외의 숫자들은 2부터 제곱근 즉 루트 n만큼까지 반복을 해주면서 나누어 떨어지는 자연수가 있는지 확인한다. 나누어 떨어지는 수가 없다면 소수로 판정한다. 여기서 루트 n까지 반복해주는 이유는 만약 n이 소수가 맞다면, n의 제곱근보다 큰 수로 나눠지지 않는다는 규칙이 있기 때문이다.
전체 코드
#소수(Prime Number)란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수.
from itertools import permutations
def solution(numbers):
def get_combinations(numbers): # get_combinations 함수 정의, 숫자의 모든 조합을 생성
combinations = [] # 조합을 저장할 빈 리스트 초기화
for i in range(1, len(numbers) + 1): # 조합의 길이를 1부터 numbers 리스트의 길이까지 반복
perms = permutations(numbers, i) # 현재 길이 i의 순열 생성
combinations += [int(''.join(perm)) for perm in perms] # 순열을 문자열로 결합하고 정수로 변환하여 리스트에 추가
return combinations # 모든 조합을 반환
#주어진 숫자가 소수인지 판단
def is_prime(n):
if n < 2: # 주어진 숫자가 2 미만인 경우
return False # False 반환 (소수는 2 이상이어야 함)
for i in range(2, int(n ** 0.5) + 1): # 2부터 루트 n까지 반복
if n % i == 0: # 만약 n이 현재의 i로 나누어 떨어지면
return False # False 반환 (n은 소수가 아님)
return True # 모든 조건을 통과하면 True 반환 (n은 소수)
combinations = get_combinations(numbers) # 입력 숫자로 가능한 모든 조합을 생성
prime_count = 0 # 소수의 개수를 저장할 변수 초기화
for num in set(combinations): # 중복 조합을 제거하기 위해 set 사용하며 각 조합을 반복
if is_prime(num): # 현재 숫자가 소수인지 확인
prime_count += 1 # 소수인 경우 prime_count 1 증가
return prime_count # 소수의 개수 반환
numbers = "17"
print(solution(numbers))