[프로그래머스] 소수 찾기 /파이썬 /Python /완전탐색

💡solutions )

✅ itertools 모듈에서 combination을 사용하기 보다는 dfs로 직접 조합 함수를 구현했다(경우의 수들은 중복 불가)

✅ 소수는 숫자 본인과 1로만 나눌 수 있는 수 (1과 본인만 약수)

✅ 소수인지 아닌지 판변하는 방법은 2부터 시작해서 판별하기 위한 해당 숫자까지로 범위 안에 있는 숫자로 전부 나누어 보고, 나누어 떨어지는 경우가 있으면 소수가 아닌 것으로 판별할 수 있다. 즉, 나누어 떨어지는 수가 없다는 것은 해당 숫자가 소수라는 것.

✅ 함수 구현시 전역변수, 지역변수 사용하는 게 아직 헷갈린다.

 

🎫code )

def solution(numbers):
    # 아래는 주어진 숫자로 나타낼 수 있는 모든 숫자의 경우를 구하는 로직(중복불가)
    def dfs(word):
        if len(word) == k: # 문자길이가 k이면 결과 리스트에 넣기
            result.add(int(word))
            return

        for i in range(n):
            if visit[i] == 0:  # 방문하지 않았다면 word문자열에 붙이기
                visit[i] = 1
                dfs(word + numbers[i])
                visit[i] = 0  # 방문 리스트 복구

    result = set() # 중복을 없애기 위해서 set 자료형으로 설정
    numbers = list(numbers)
    n = len(numbers)
    visit = [0] * n
    for k in range(1, n + 1):
        dfs("")

    # 여기서부터 소수 찾는 로직
    answer = 0
    for i in result:
        if i == 1 or i == 0:
            continue
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            answer += 1
            print(answer)
    return answer

 

📌 description )

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3

코딩테스트 연습 - 소수 찾기

 

문제 설명

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

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