[Python] 코딩테스트 고득점Kit | 완전탐색2-소수찾기

아래의 문제는 프로그래머스 코딩테스트 고득점 Kit 내용이며 코드는 직접 푼 내용입니다.

---

소수찾기

문제상황

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

 

요구사항

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

종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수

 

제한사항

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

입출력

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있어서 -> 리턴3

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있어서 -> 리턴2 ( 단, 11과 011은 같은 숫자로 취급한다)

---

풀이과정

우선 입출력예시에서 나와있는 것 처럼 문자열을 int리스트로 바꿔야겠다고 생각이 들었다.

그리고 소수인지 아닌지 가능한 숫자들을 조합으로 뽑아서, 그 안에서 소수를 찾으면 될까 싶었다. 

 

결과

내가 푼 정답코드결과

from itertools import permutations
def is_sosu(num):
    if num==0 or num==1:
        return False
    else:
        for n in range(2, (num//2)+1):      # math를 사용하지 않고 (num//2)+1 까지로 설정
            if num%n == 0:
                return False
        return True
        
def solution(numbers):
    answer = 0
    pre_list =[]
    num_list = list(map(int,numbers))
    print(num_list)
    
    for i in range(1,len(numbers)+1):
        for j in permutations(numbers,i):
            pre_list.append(''.join(j))
    pre_list = list(map(int,pre_list)) #0제거 : int
    pre_list = list(set(pre_list)) #중복제거
    
    for i in pre_list:
        if is_sosu(i):
            answer +=1
    return answer

 

모든 경우의 수를 가져오는 조합 사용할때, 

 for j in list(permutations(numbers,i)): print(i) 라면

('0',) ('1',) ('1',)

('0', '1') ('0', '1') ('1', '0') ('1', '1') ('1', '0') ('1', '1')

('0', '1', '1') ('0', '1', '1') ('1', '0', '1') ('1', '1', '0') ('1', '0', '1') ('1', '1', '0') 

이런식으로 string이 아닌 튜플값으로 리턴된다. 

그래서 string값으로가져오기 위해 ''.join(j)를 쓰면 아래처럼 string값으로 리턴받을 수 있다. 

0 1 1 01 01 10 11 10 11 011 011 101 110 101 110 

 

배운점

• map(바꿀형, 대상) : 문자열이였던 
• set : 중복제거
• permutations : 조합

---

참고 

참고한 블로그 링크