[프로그래머스] 완전 탐색(+재귀), 소수 찾기

결론: 레벨2인데 많이 어려웠다 !!!!ㅜㅜ

재귀는 아직 나에게 익숙하지 않았고 + 소수 찾는 아이디어도 익혀야했다. (에라토스테네스의 체 등.)

덕분에 순열 알고리즘도 공부했고, 소수 찾기 유형은 앞으로 껌이 될 예정🤩 매일매일 재귀랑 더 친해지는 중

사실 재귀 알골 대신 훨씬 효율 좋은 파이썬 모듈(itertools-permutations)이 있는데,

배운 것 적용도 해보고 모듈 의존적이지 않기 위하여 두 가지 방식 각각 시도해보았다

 

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

프로그래머스

문제 개요

input
숫자가 적힌 문자열 numbers
*길이 1 이상 7 이하인 문자열
*각 숫자는 0~9
*"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다

return
흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지, 소수 개수

EX
"17" -> 3
"011" -> 2

 

Idea

• 순열 구하는 방법(1. permutations 모듈 2. 재귀) : 👉 https://lets-hci-la-ai-withme.tistory.com/47
• 소수 구하는 방법:👉 https://velog.io/@cjy0029/소수-구하는-방법 
  • 소수에는 1 미포함, 2,3,... 포함
  • N의 소수 판별: 2부터 N-1까지 루프를 돌면서 나눠보는 방법(나머지가 없을 때)
    • 비효율적
  • "어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 규칙이 있다."
  • 에라토스테네스의 체
    • 2부터 순회를 하면서 2의 배수를 모두 지워주고, 3부터 순회를 하면서 3의 배수를 모두 지워주고, 4는 이미 지워졌으니 패스하고, 5의 배수를 지우고..
    • 주어진 수의 제곱근까지만 확인해보면 끝난다.

1. python itertools-permutations 활용

 

from itertools import permutations
def solution(numbers):
    nums = []
    for i in range(len(numbers)):
        nums += [int(''.join(x)) for x in list(permutations(numbers, i+1))]
    
    answers = []
    answers += [x for x in nums if (x in [2,3])]
    for x in nums:
        sqrt = int(x**(1/2))
        for i in range(1,sqrt):
            if x % (i+1) != 0:
                if i+1 == sqrt:
                    answers.append(x)
                continue
            else:
                break
    nums = len(set(answers))
    return nums

2. 재귀 알골 이용

def solution(numbers):
    answers = []
    def permutation(numbers, r):
        used = [0 for _ in numbers]
        def generate(chosen, used):
            if len(chosen) == r:
                chosen = int(''.join(chosen))
                if (chosen in [2,3]) and (chosen not in answers): #2,3은 sqrt값이 1이므로 이하 for문이 실행되지 않음
                    answers.append(chosen)
                
                sqrt = int(chosen**(1/2))
                for i in range(1, sqrt):
                    if chosen % (i+1) != 0:
                        if (i+1 == sqrt) and (chosen not in answers):
                            answers.append(chosen)
                            break
                        continue
                    else:
                        break
                return

            for i in range(len(numbers)):
                if not used[i]:
                    chosen.append(numbers[i])
                    used[i] = 1
                    generate(chosen, used)
                    used[i] = 0
                    chosen.pop()

        generate([], used)

    for i in range(len(numbers)):
        permutation(numbers, i+1)
    answer = len(answers)
    return answer

 

• append 하기 전, 중복 제거 필요
•  '구분자'.join(리스트)
  • map(''.join, 리스트)로 처리하면 빠름
• 순열 알고리즘 내에서, 모든 단어를 리스트에 저장하는 것이 아니라, 소수인 것만 filter 해서 저장 ←이때 에라토스테네스의 체