[Programmers] Find a Decimal Number.py (complete search)

#. Problem

https://programmers.co.kr/learn/courses/30/lessons/42839

* The copyright in this matter is in Programmers

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

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 

종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 주어진 한자리 숫자의 조합으로 소수가 몇 개 만들어질 수 있는지

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 우선 주어신 한자리 숫자로 만들 수 있는 숫자의 조합을 만들어 본다.

  2. 그 조합들이 소수인지 아닌지 판별한 후, 소수이면 answer += 1

  3. 말은 쉽다..

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

from itertools import permutations def solution(numbers):     answer = 0     numbers = list(numbers)     all_num = []     for i in range(len(numbers)):         for j in permutations(numbers,i+1):             all_num.append(int(''.join(j)))       for num in set(all_num):         flag = True         if num != 1 and num != 0:             for di in range(2, num) :                 if num % di == 0 :                     flag = False                     break             if flag == True: answer += 1     return answer

cs

  - 리스트에서 가능한 순열 구하기

    itertools.permutations 함수 (https://docs.python.org/2/library/itertools.html#itertools.permutations)

    (6~8) numbers의 크기(주어진 숫자의 개수)만큼 가능한 순열을 구함

            ex. permutations(numbers,2) 의 결과로는 [('1', '7'), ('7', '1')] 이러한 형태로 나오는데,

               ''.join(j) 으로 리스트 안의 문자들을 하나씩 합쳐주면 '17' 형태로 나오게 됨. 

               이렇게 나온 결과들을 int로 형변환 시켜주고 list에 append

    (10~17) 같은 숫자가 여러개 주어질 경우 중복이 발생할 수 있으므로 중복을 제거해주는 set 자료형으로

               변환된 list의 요소를 하나씩 꺼내어 소수인지 확인

               2부터 각 요소에 해당하는 수-1 까지 0으로 나누어지는 수가 존재하는지 flag 변수로 확인

               0으로 나누어지는 수가 없다면 그 수는 소수이므로 소수 개수(answer)를 1 증가              

#. Other code

1 2 3 4 5 6 7 8 9

from itertools import permutations def solution(n):     a = set()     for i in range(len(n)):         a |= set(map(int, map("".join, permutations(list(n), i + 1))))     a -= set(range(0, 2))     for i in range(2, int(max(a) ** 0.5) + 1):         a -= set(range(i * 2, max(a) + 1, i))     return len(a) Colored by Color Scripter

cs

  - (5) 본인 코드의 6~8번 과정을 map을 활용하여 한 줄에 표현

    (6) set 요소에 0,1이 있다면 제거, set 자료형에서 | 는 합집합을 의미

    (7~8) 에라토스테네스 체를 set을 이용하여 코딩한거라는데 어렵다..