코딩/코딩테스트

프로그래머스_완전탐색_레벨2_소수찾기

윤유상 2021. 5. 14. 21:48

 

 

 

문제

 

문제 설명

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

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

 

제한사항

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

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

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

 

 

 

내 풀이

# 내 풀이, 최대 시간: 1085.89ms
import itertools
def isPrime(n):
    if n <= 1:
        return False
    elif n > 2 and n % 2 == 0:
        return False
    elif n > 3 and n % 3 == 0:
        return False
    elif n > 5 and n % 5 == 0:
        return False
    for i in range(7, (n // 2) + 1):
            if n % i == 0:
                return False
    return True

def solution(numbers):
    combList=[]
    for i in range(1, len(numbers) + 1):
        comb = itertools.permutations(numbers, r=i)
        combList += [int("".join(x)) for x in list(comb) if isPrime(int("".join(x)))]
    combSet = {x for x in combList}
    return len(combSet)

 

해결법

우선 d 값을 몇 개의 숫자와 비교했습니다, 0, 1, 2가 아닌 2의 배수, 3이 아닌 3의 배수, 5가 아닌 5의 배수면 소수가 아니기 때문에 False를 리턴합니다. 그리고 7부터 (n // 2) + 1까지 검사하면서 소수인지 아닌지 찾습니다.

그 다음엔 1부터 len(numbers)까지 자리수를 높이면서 문자열을 이용해 만들 수 있는 숫자 중 소수인 값을 모두 comblist에 넣습니다.

모든 경우의 수를 구한 다음엔, 중복을 없애기 위해 모든 값을 set에 넣고 몇 개인지 반환합니다.

 

 

문제점, 보완할 점

리스트에 넣고, sets에 집어넣는 식으로 불필요한 과정이 있었습니다.

 

 

 

모범 풀이

# 모범 풀이, 최대 시간: 690.93ms
from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

해결법

우선, 만들 수 있는 모든 경우의 수를 구해서 set에 넣습니다. 그 다음 set에서 0과 1을 제거합니다.

2부터 set에 저장된 값 중 가장 큰 값의 루트 값까지 i를 하나씩 올려가며, i 값을 제외한 i의 배수의 숫자를 set에서 제거합니다.

남은 숫자의 개수를 반환합니다.

 

 

배울점

set(map(...))으로 set에 값들을 바로 넣고, a -= set(...)로 값을 제거했습니다.

set를 잘 몰랐는데, set에 다른 set를 빼서 값을 쉽게 제거할 수 있다는 걸 배웠습니다.

map안에 int를 인자로 줘서 저장된 값을 모두 int로 쉽게 바꿀 수 있다는걸 배웠습니다.

 

 

 

반응형