[프로그래머스] 완전탐색 2. 소수 찾기

문제

---

풀이

로직은 금방 생각 났는데 구현에서 오래 걸렸다.

에라토스테네스의 체도 간단하다고 생각했는데 구현에서 버벅댔다. 

풀이는 다음과 같다.

1. 모든 숫자 조합을 allNums에 저장한다.

2. 그 중 가장 큰 수까지 에라토스테네스의 체로 소수를 찾는다.

3. 두 리스트의 교집합을 찾는다.

from itertools import permutations

def solution(numbers):
    answer = 0
    
    allNums = []
    for i in range(1, len(numbers) + 1):
        temp = list(permutations(list(numbers), i))
        for i in temp:
            allNums.append(int(''.join(i)))
    
    n = max(allNums)
    eratos = [False,False] + [True] * (n-1)
    primes = []

    for i in range(2, n+1):
        if eratos[i]:
            primes.append(i)
            for j in range(2*i, n+1, i):
                eratos[j] = False
    
    s1 = set(primes)
    s2 = set(allNums)
    print(s1&s2)
    
    return len(s1&s2)

---

새로 알게 된 문법

1. list(string)

  이렇게 string에 list()를 씌워주면 "17"은 ["1", "7"]로 끊겨 저장된다.

2. itertools.permutations() 

  중복 조합을 반환한다.

3. set1 & set2

  교집합

---

다른 분의 코드

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)

로직은 비슷한 것 같은데

에라토스테네스의 체를 따로 만들지 않고 바로 제거한 것 같다.

근데 두 번째 포문의 max(a) ** 0.5가 잘 이해 안 간다.

왜 max의 루트까지지,, 이제 슬슬 노트를 들고 다녀야겠다.,,

# 0으로 시작하는 숫자. 
# 모든 숫자의 조합.

def isPrimeNumber(number):
    if number <= 1:
        return False
    else:
        for i in range(2, number // 2 + 1):
            if number % i == 0:
                return False
        return True

def getAllCombination(numbers, numList, leftCipher):
    '''
    numbers : 총 숫자카드 list
    numList : 가능한 숫자 배열 list
    leftCipher : 남은 자릿수
    '''

    # 현재 가능한 숫자 배열 list를 기준으로 추가가 가능한 숫자들은 찾는다. 
    newNumList = [[]]
    for li in numList:
        for i in numbers:
            if i in li and li.count(i) <= numbers.count(i) - 1:
                tmp = li[:]
                tmp.append(i)
                newNumList.append(tmp)
            if i not in li:
                tmp = li[:]
                tmp.append(i)
                newNumList.append(tmp)

    leftCipher -= 1

    if leftCipher == 0:
        return newNumList
    else:
        return getAllCombination(numbers, newNumList, leftCipher)

def removeFirstZero(numList):
    for i, num in enumerate(numList):
        firstNumIsZero = bool()

        while True:
            if len(num) >= 2 and num[0] == '0':
                firstNumIsZero = True
            else:
                numList[i] = num
                break

            num = num[1:]

def getUnique2DList(numList):
    for i, val in enumerate(numList):
        tmp = str()
        for char in val:
            tmp += char
        numList[i] = tmp

    newList = list(set(numList))
    return newList

def solution(numbers):    
    availableAnswer = getAllCombination(numbers, [[]], len(numbers))
    del availableAnswer[0]
    removeFirstZero(availableAnswer)
    availableAnswer = getUnique2DList(availableAnswer)

    answer = 0
    for val in availableAnswer:
        if isPrimeNumber(int(val)):
            print(val)
            answer += 1

    return answer

라이브러리 없이 직접 구현하셨다.