[프로그래머스/python] 완전 탐색 : 소수 찾기

문제 설명

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

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

 

제한 사항

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

 

정답

import itertools

def solution(numbers):
    answer = {}
    numbers = list(numbers)

    # 큰 수부터 정렬
    numbers.sort(reverse=True)

    # 가장 큰 수 조합
    max_number = ""
    for i in numbers:
        max_number += str(i)
    max_number = int(max_number)

    # 소수 True로 저장하기
    idx = [True for i in range(max_number + 1)]
    idx[0] = False
    idx[1] = False
    for i in range(2, int(max_number**0.5)+1):
        if idx[i]:
            for j in range(2*i, max_number+1, i):
                idx[j] = False
	
    # 숫자 조합 찾기
    for i in range(1, len(numbers)+1):
        target = list(map(''.join, itertools.permutations(numbers, i)))
        for j in target:
            if int(j) not in answer:
                answer[int(j)] = idx[int(j)]

    result = 0
    for v in answer.values():
        if v == True:
            result += 1
    return result

---

numbers = list(numbers)

# 큰 수부터 정렬
numbers.sort(reverse=True)

# 가장 큰 수 조합
max_number = ""
for i in numbers:
    max_number += str(i)
max_number = int(max_number)

받은 숫자리스트를 내림차순으로 정렬하여

조합하여 나올 수 있는 가장 큰 수인 max_number를 구한다.

 

# 소수 True로 저장하기
idx = [True for i in range(max_number + 1)]
idx[0] = False
idx[1] = False
for i in range(2, int(max_number**0.5)+1):
    if idx[i]:
        for j in range(2*i, max_number+1, i):
            idx[j] = False

전에 풀었던 소수구하기 문제의 에라토스테네스의 체를 사용하여 max_number까지의 소수를 구한다.

소수구하기 문제와 에라토스테네스의 체 포스팅을 아래에 걸어두었다.

2021.03.09 - [🔍알고리즘/백준] - [백준/python] 1929번 : 소수 구하기

[백준/python] 1929번 : 소수 구하기

2021.03.10 - [🔍알고리즘/🔅개념정리] - [파이썬/python] 에라토스테네스의 체

[파이썬/python] 에라토스테네스의 체

 

# 숫자 조합 찾기
    for i in range(1, len(numbers)+1):
        target = list(map(''.join, itertools.permutations(numbers, i)))
        for j in target:
            if int(j) not in answer:
                answer[int(j)] = idx[int(j)]

numbers 리스트에 있는 숫자로 만들 수 있는 숫자 조합을 찾는다.

한자리 숫자부터 numbers의 모든 숫자를 사용하는 조합까지 반복문을 통해 구한다.

itertools의 permutations를 사용하여 순열을 쉽게 구할 수 있다.

아래는 itertools 관련 포스팅이다.

2021.04.01 - [🔍알고리즘/🔅개념정리] - [파이썬/python] 순열과 조합 : itertools 이용하기 (permutations, combinations)

[파이썬/python] 순열과 조합 : itertools 이용하기 (permutations, combinations)

answer에 해당 조합의 숫자가 없다면, answer 딕셔너리에 해당 idx 값과 함께 넣어준다.

딕셔너리에 넣는 이유는 11, 011처럼 같은 수가 중복해서 나올 수 있기 때문이다.

answer에 저장된 key의 value가 True라면 key가 소수라는 뜻이고, False라면 소수가 아니라는 뜻이다.

 

result = 0
    for v in answer.values():
        if v == True:
            result += 1
    return result

answer에 저장된 value가 True인 key를 세어 result에 저장한 후 result를 return한다.