Programmers) 소수 찾기

문제

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

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



설명


오랜만에 간단한 문제입니다.


숫자로 이루어진 특정 문자열이 들어왔을 때,
각 문자로 이룰 수 있는 숫자의 경우의 수를 탐색하고,
만들어진 숫자 중에 소수는 몇개 있는가 판단하는 문제입니다.


여기서 문제 될 거라면 각 문자의 조합 수를 판단하는 것이지만,
파이썬 에서 감사하게도 리스트의 조합(순열과 조합할 때 그 조합입니다)을 구해주는
내장 함수가 존재하기에...

그걸 활용하면 정말 간단하게 풀 수 있겠습니다.


먼저 제가 찾은 규칙을 설명하고 바로 코드 리뷰 시작하겠습니다.
  1. "011"과 "11"은 같은 숫자로 취급한다는 조항은 int 강제 형변환을 통해 구현할 수 있다. "011"을 정수형으로 형 변환 시 11로 바뀐다.
  2. 순서도 판단해야 하기에 '조합' 대신 '순열'을 사용한다.
  3. 순열로 조합 수를 구하고, Set을 이용해 중복 값들을 전부 제거한다.
  4. 소수는 1과 자기 자신 외에 나누어 떨어지는 게 없는 수다.
이 규칙들을 그대로 코드로 옮기면 되겠습니다.


from itertools import permutations as pmt

def prime_chk(num):
    if num <= 1:
        return False
    for chk in range(2, num):
        if num % chk == 0:
            return False
    return True

def solution(numbers):
    comb_ls = {int("".join(comb)) for idx in range(1,len(numbers)+1) for comb in list(pmt(numbers,idx))}
    return len([num for num in comb_ls if prime_chk(num)])


Main 되는 코드 부분이 전부 리스트 컴프리헨션으로 구성된 모습을 볼 수 있습니다 ㅎㅎ...


아무래도 그냥 for문, append를 활용하는 것 보다 성능이 좋다는 글을 보고 난 뒤로
대충 코드 짜기 좀 그렇더라구요.


뱀발이지만 리스트 컴프리헨션에 대한 정리 글 또한 일일 파이썬으로 올려놨으니,
궁금하신 분들은 한번 보고 오셔도 좋을 것 같습니다. 링크 달아 두겠습니다.




다시 코드 리뷰로 돌아와서,


comb_ls는 경우의 수를 담아 두는 Set 데이터 입니다. 과정은 아래와 같이 진행됩니다.
  1. 받아온 숫자의 개수를 세서 생성 가능한 자리수를 산출
  2. 자리수와 숫자를 파이썬 내장함수 Permutations(리스트의 경우의 수를 순열로 구해 리스트로 반환합니다.)에 넣어 경우의 수를 받아온다. (튜플로 조합이 묶인 리스트가 반환됩니다.)
  3. 경우의 수를 다시 반복문을 돌리면서 하나하나 씩 가져오고, 숫자로 바꾸는 전처리 과정을 거친다.

이렇게 경우의 수를 정수형 숫자로 바꾼 리스트를 다시 반복문을 돌려 값을 하나하나씩 가져옵니다.


저는 미리 소수를 판별하는 함수를 구축해놨습니다.
위에서 가져온 숫자들을 함수에 넣어 소수가 아닐 때는 False를 반환하게 만들었습니다.


처음에는 For문으로 '소수 판별 함수에서 나온 True 갯수를 세라' 라고 만들었으나,
이것도 한 줄로 만들고 싶어서 결국 컴프리헨션에 적용했습니다.


반환 파트는
  • 소수인 숫자로 구성된 리스트를 만들고
  • 그 리스트의 크기
를 구하도록 만들었습니다.




요새 일이 많아진 관계로
블로그 업로드가 많이 어려워졌습니다...


그래도 오늘(020616)은 짬이 나서
간단한 문제라도 풀어서 리뷰할 수 있었습니다.


개인 공부나 업무를 진행하면서 괜찮은 프로그래밍 적 정보가 있으면


언제든지 가져와서 업로드 하겠습니다.


이만 글을 마치겠습니다.

댓글

댓글 쓰기