[Lv.2] 소수 찾기

문제

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

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한 조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

Link

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

프로그래머스

 

code

def solution(numbers):
    result = []
    prev_elements = []
    answer = 0

    def dfs(elements):
        
        result.append(''.join(prev_elements[:]))
        
        for e in elements:
            next_e = elements[:]
            next_e.remove(e)
            prev_elements.append(e)
            dfs(next_e)
            prev_elements.pop()
            
    dfs(list(numbers))
    
    # 리스트 앞 [] 제거
    result.pop(0)
    result = list(set(map(int,result)))
    
    for i in result:
        if i == 0 or i == 1: # i < 2로 수정 가능
            continue

        for j in range(2,i):
            if i % j == 0:
                break
            # j가 i-1 까지 돌아도 소수 없다면 정답에 추가
            if j == i-1:
                answer +=1
    return answer

 

2일째 오류 찾고 있는데 못찾음

test case 1,2,5,6,10,11 오류 남

 

2022.08.28 update

code

from itertools import permutations
def solution(numbers):

	# 소수 판별 함수
    def decision(num):
    	# 0,1은 소수가 존재하지 않음
        if num < 2 :
            return False
        # 범위를 제곱근 까지로 한정
        for i in range(2, int(num**0.5)+1):
            if num % i == 0:
                return False
        return True
    
    answer = 0
    result = []
    for i in range(1,len(numbers)+1):
        p = list(permutations(numbers,i)) 
        # 2번째 인자 값 지정 안하면 default로 len(list)가 들어간다.
        for j in p:
            result.append(int(''.join(list(j))))
    result = list(set(result))

	# 소수 판별 반복문
    for num in result:
        if decision(num):
            answer +=1
    return answer

1. 순열 개념 적용

- Python 에서 제공하는 itertools 라이브러리의 permutations 함수를 import

 

Permutations(list,num)

1) 정의: 순열 계산 함수

2) 매개변수: 첫번째 인자로 순열을 계산 할 list, 두번째 인자로 순열 길이를 입력한다. 2번째 매개변수는 입력하지 않으면 default 값으로 list의 길이가 주어진다.

 

2. 중복 함수 사용

- 소수를 판별하는 과정에서 2중 반복문 사용시 계산이 중복되는 오류가 발생하여, 소수 판별  부분을 중복 함수로 정의하여, 하나의 반복문에서 함수를 호출하였다.

 

3. code 순서

- 길이별로 반복문을 돌며 순열의 조합하여 list에 추가한다.

- 이때 permutations 함수 각 원소의 return 값은 tuple이므로

# return 값 예시 [('1',), ('7',)]

두번째 반복문 실행시 result.append(int(''.join(list(j)))) 처리를 하여 원소를 list로 만든 후 join 함수를 이용하여 하나의 문자열로 만들고, 이를 int 형으로 변환하여 list에 저장 한다.

* int 형 변환 이유: '000', '031' 과 같은 문자열에서 0을 제거하기 위하여

 

-  list(set(result))의 의미: 중복 원소 제거

앞의 과정에서 만들어진 list의 경우 원소가 중복되는 경우가 생긴다. set() 은 중복 원소를 포함하지 않는 자료형으로 result를 set형으로 변환 후 다시 list형으로 만들면 중복 원소가 제거 된다.