[프로그래머스.42839] 완전탐색 - 소수찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

입출력

• 첫 번째 입력의 1과 7로 얻을 수 있는 숫자의 조합은 [ 1, 7, 17, 71 ]이다.
• 이때, 소수는 7, 17, 71 총 3개이므로 3을 반환한다 
• 두 번째 입력의 0과 1, 1로 얻을 수 있는 숫자의 조합은 [0, 1, 10, 11, 101, 110]이다. 
• 이때, 소수는 11, 101으로 총 2개이므로 2를 반환한다

 

의식의 흐름

먼저 입력값으로부터 얻을 수 있는 숫자의 조합을 구하기 위해서는 순열이나 조합을 활용해야하나 싶었다

그래서 먼저 순열과 조합의 개념과 파이썬으로 구현하는 방법을 정리했다 → [Python] 순열과 조합

그다음 특정 값이 소수인지를 판별하는, 혹은 특정 범위 내의 소수의 개수를 구하는 공식이 있을 것이라고 생각해서 찾아보니

제곱근을 활용하는 방법과 에라토스테네스의 체 방법이 있었다. 그래서 먼저 개념 정리를 하고, 문제를 풀었다.

 

풀이

1. 입력값을 통해 조합 가능한 경우의 수(cases)를 모두 구한다

    - (1,0)과 (0,1) 은 서로 다른 조합이다. 숫자로 치환하면 10과 1이므로 서로 다른 값이다. 

    - 위와 같은 이유로 중복을 허용해야 하기 때문에 순열을 사용한다

    - nCr 에서 r = 1, r = 2 ... r = n 까지 모든 경우의 수를 찾아 배열에 저장한다

    - 숫자로 치환했을 때 같은 값이 있다면 제거한다 

 

2. 경우의 수(cases) 중, 소수의 개수를 센다

    - cases에 0과 1이 있다면, 0과 1은 소수가 아니므로 cases에서 제거한다

    - 특정 범위 내의 소수의 개수를 구하는 것이 아니라, 값이 소수인지를 판별해야 하므로 제곱근을 활용한다

 

 

Python

import math
import itertools

def solution(numbers):    
    cases = get_cases(numbers)          # 1. 경우의 수 구하기
    answer = get_prime_numbers(cases)   # 2. cases 중, 소수의 개수 구하기
    return answer    
        
        
# 1. 경우의 수 구하기        
def get_cases(numbers):
    nums = [int(num) for num in numbers] 
    nPr = []
    
    # 경우의 수를 모두 구한다
    # (1,0) 과 (0,1) 은 다르다 → 10 != 1 → 중복이 허용되는 순열을 사용
    for i in range(1, len(nums)+1):
        nPr += list(itertools.permutations(nums, i))
    
    # (1,0) 의 형태를 숫자로 변경 → 10
    cases = list(set(int(''.join([str(t) for t in temp])) for temp in nPr))
    return cases

    
# 2. cases 중, 소수의 개수 구하기    
def get_prime_numbers(cases):
    answer = 0
    if 0 in cases: cases.remove(0)   # 0은 소수가 아니므로 제거
    if 1 in cases: cases.remove(1)   # 1은 소수가 아니므로 제거
        
    for case in cases:
        check = True                 # 소수인지 확인
        sqrt = int(math.sqrt(case))  # 제곱근 구하기
        
        # 2 이상, 제곱근 이하의 숫자로 나누어떨어지는 지 확인
        for s in range(2, sqrt+1):   
            if case % s == 0:
                check = False 
                break
        
        # 소수라면 answer +1
        if check : answer += 1 
            
    return answer

 

Java

// 추가 예정

코딩테스트 연습 - 모의고사