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

소수의견을 존중하자

문제 풀이 정리

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

코드

def solution(numbers):
    answer = 0
    from itertools import permutations
    num_list = []
    for num in numbers:
        num_list.append(num)
    check_set = set()
    for i in range(1, len(num_list)+1): # 1자리숫자부터 n자리 숫자까지 생성을 위한 반복
        for num in list(permutations(num_list,i)): # 경우의 수로 생성. permutation(순서중요)
            num_string = "".join(num)
            number_int = num_str2int(num_string)
            
            if number_int in check_set: # 한번 검사한건 제끼기
                continue
            
            if primeCheck(number_int): # 소수면 count += 1
                answer += 1
                check_set.add(number_int)
    return answer

def num_str2int(num): #문자를 숫자로
    return int(num)

def primeCheck(num): # 소수 판별 함수
    import math
    if num < 2:
        return False
    else:
        check_num = int(math.sqrt(num))
        for n in range(2, check_num+1):
            if num % n == 0:
                return False
    return True

 

문제 넋두리

 

완전 탐색문제 인데, 두가지를 알아야 풀 수 있었다.

조합을 만들 수 있는지? => permutaion, combination 문제인지 파악 및 적용가능?

소수 판별을 할 수 있는지? => 소수의 성질을 이용할 수 있는지?

 

1. 첫번째 : 조합을 만들수 있는지

- 이전 알고리즘 문제들을 통해 조합사용을 위한 모듈 불러오기를 몇번 반복하면서 익숙해졌다.

다만, permutation (순서 중요, 중복0) 인지 combination(순서 x, 중복x) 인지 파악하는게 중요하다

 

2. 두번째 : 소수 판별을 할 수 있는지

- 소수가 몇개인지의 문제는 많이 풀어보았다 (에라토스테네스의 체 문제들)

그래서 그런지 그렇게 어렵지 않았다.

자기 자신의 제곱근 까지 숫자가 나눠지지 않으면 소수로 합격~

 

두가지가 조합된 아주 좋은 문제였다

그런데 자꾸 틀렸던 이유는 python의 경우 for(int i = 0; i < num; i++) 식의 문법이 아니여서 그런지 range 함수가 num 까지 돌아가는지 아닌지 자꾸 헷갈렸기 때문이다.