문제 출처 : 프로그래머스 - programmers.co.kr/learn/courses/30/lessons/42839

문제 설명

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

입출력 예 설명

• 예제 #1

  [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

• 예제 #2

  [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

코드 풀이

접근방식

1. 순열조합 라이브러리를 이용해서 경우의 수를 구하기

• nPm : n개의 숫자를 m개로 순열!(순서 상관 있는 것= 순열)

• 현재 필요한 순열 : nP1, nP2, ....nPn 까지 모두

  • 그래서 all_numbers list에 append해줌.

• 코드 :

all_numbers.append(list(permutation({해당 리스트이름},m))

• 출력 결과 : [[('1',), ('1',), ('0',)], [('1', '1'), ('1', '0'), ('1', '1'), ('1', '0'), ('0', '1'), ('0', '1')], [('1', '1', '0'), ('1', '0', '1'), ('1', '1', '0'), ('1', '0', '1'), ('0', '1', '1'), ('0', '1', '1')]]

2. 각 순열마다 문자열로 바꾸어주어서 int 정수형으로 저장해주기

• 이 때, 중복되는 부분을 제거해주기 위해 set 집합 자료형을 이용해줌.

• 3중 for문 -> 완전 탐색 하는 부분

• 출력 결과 : [0, 1, 10, 11, 101, 110]

3. 집합자료형 set 을 list로 바꿔주기

• set은 인덱싱이 불가하여 각 원소마다의 접근이 어렵기 때문에 list로 바꾸어주어야 한다.

• 방법 : sorted(set이름) 사용함. (더 많은 방법은 아래 link 참고)

{list이름}=sorted({set이름})

4. 소수인지를 판별해준다.

• math 라이브러리의 제곱근 math.sqrt(n) 을 이용해서 반복 횟수를 줄여준다. !!

• 나머지가 0 : 즉 나누어 떨어진다면, point 변수를 통해 계수에서 제외한다.

from itertools import permutations
import math


def solution(numbers):
    answer = 0
    all_numbers = []
    # numbers 길이만큼 순열 구하기! 1<=n<=len(numbers)
    for n in range(1, len(numbers) + 1):
        all_numbers.append(list(permutations(numbers, n)))

    # list를 문자열로 바꾸어서 집합 set()에 넣기 (중복 x)
    set_numbers=set()
    for i in range(len(all_numbers)):
        for j in range(len(all_numbers[i])):
            temp='' # 각 순열 별로 문자열로 만들어주기
            for k in range(len(all_numbers[i][j])):
                temp = temp + all_numbers[i][j][k]
            # 저장한 문자열을 int형으로 set에 넣어주기 (0이 앞에 나오는 것 제거해줌)
            set_numbers.add(int(temp))

    # 소수 판별 및 count!
    # 인덱싱을 위해 set 데이터를 list로 옮겨주기
    last_list = sorted(set_numbers)
    # print(last_list)
    for n in last_list:
        if n==2:
            answer=answer+1
        elif n>2:
            point = True
            for i in range(2,int(math.sqrt(n))+1):
                if n%i==0:
                    point=False
                    break
            if point==True:
                answer=answer+1
    return answer

print(solution("17"))

결과

- 참고 :www.geeksforgeeks.org/python-convert-set-into-a-list/